DMOPC '14 Contest 7 P6 - Revenge of the Bins

View as PDF

Submit solution

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

Problem types

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.


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

3 5 4 2 1 6

Sample Output



There are no comments at the moment.