Tusk has ~N~ ~(2 \le N \le 10^5)~ bins arranged in a line. ~N~ is even. The ~i~-th bin has size ~s_i~ ~(1 \le s_i \le N)~. The sizes are distinct, so they form a permutation of the numbers from ~1~ to ~N~. Tusk wants to take the largest possible prefix of the bins so that he can fit the bins from the second half of the prefix into the first half of the prefix.

Formally, find the maximum ~x~ ~(1 \le x \le \dfrac{N}{2})~ such that there is a permutation ~p_1, p_2, \dots, p_x~ of the numbers ~1~ to ~x~ so that for each ~i~ from ~1~ to ~x~, ~s_i > s_{x+p_i}~. If there is no such ~x~, output 0.

For example, if the bins' sizes are 3, 5, 4, 2, 1, 6, then the only valid value of ~x~ is ~2~. ~x=2~ is valid because you can fit bin 3 into bin 2 and bin 4 into bin 1. ~x=1~ is invalid because you can't fit bin 2 into bin 1. ~x=3~ is invalid because bin 6 can't fit into bin 1, 2, or 3.

Input Specification

The first line contains ~N~. The next line contains ~N~ integers: the sizes of the bins.

Output Specification

Output a single integer: the maximum value of ~x~.

Constraints

Subtask 1 [10%]

~N \le 10~

Subtask 2 [10%]

~N \le 1\,000~

Subtask 3 [10%]

~N \le 10\,000~

Subtask 4 [70%]

~N \le 100\,000~

Sample Input

6
3 5 4 2 1 6

Sample Output

2