Tusk has bins arranged in a line. is even. The -th bin has size . The sizes are distinct, so they form a permutation of the numbers from to . 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 such that there is a permutation of the numbers to so that for each from to , . If there is no such , output
For example, if the bins' sizes are 3, 5, 4, 2, 1, 6, then the only valid value of is . is valid because you can fit bin 3 into bin 2 and bin 4 into bin 1. is invalid because you can't fit bin 2 into bin 1. is invalid because bin 6 can't fit into bin 1, 2, or 3.
The first line contains . The next line contains integers: the sizes of the bins.
Output a single integer: the maximum value of .
- Subtask 1 [10 points]:
- Subtask 2 [10 points]:
- Subtask 3 [10 points]:
- Subtask 4 [70 points]:
6 3 5 4 2 1 6