## DMOPC '14 Contest 8 P6 - Revenge of the Bins

View as PDF

Points: 20 (partial)
Time limit: 0.6s
Memory limit: 256M

Author:
Problem types

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 0.

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.

#### Input Specification

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

#### Output Specification

Output a single integer: the maximum value of .

#### Sample Input

6
3 5 4 2 1 6

#### Sample Output

2