A. Random Order
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You discovered that the problems in the contest were shuffled, so you want to analyze their difficulty.

You assume that the difficulty of each of the $$$n$$$ problems is described by a permutation $$$p = (p_1, \cdots , p_n)$$$ (a permutation of length $$$n$$$ contains each of the numbers from $$$1$$$ to $$$n$$$ exactly once).

For each number $$$k$$$, you want to determine whether the $$$k$$$ easiest problems (numbered $$$1, \cdots , k$$$) appear in the permutation strictly earlier than the $$$k$$$ hardest problems (numbered $$$n, \cdots , n-k+1$$$).

Let the indices of the $$$k$$$ easiest problems be given by the set $$$A_k$$$, and the indices of the $$$k$$$ hardest problems by the set $$$B_k$$$.

Then, for a given number $$$k$$$, it is necessary to check that for any $$$a \in A_k, b \in B_k$$$, the inequality $$$a \lt b$$$ holds.

You need to find the maximum possible $$$k \ge 1$$$ for which the corresponding sets $$$A_k, B_k$$$ satisfy the condition above, or report that no such $$$k$$$ exists.

Input

The first line contains an integer $$$n (1 \le n \le 10^5)$$$ — the number of problems in the contest.

The second line contains $$$n$$$ numbers $$$p_1, p_2, \ldots, p_n\, (1 \le p_i \le n)$$$ — a permutation describing the difficulty of the problems. It is guaranteed that each of the numbers from $$$1$$$ to $$$n$$$ appears exactly once.

Output

In the only line, output the maximum possible $$$k \ge 1$$$ satisfying the condition of the problem.

If no such $$$k$$$ exists, output $$$-1$$$.

Examples
Input
7
1 4 2 3 5 7 6
Output
3
Input
3
3 2 1
Output
-1