Find Array Uniqueness Median

Sort the numbers of distinct values of all non-empty contiguous subarrays and return the median; when the length is even, take the smaller of the two middle values.

输入格式

The first line contains n (1..100000), and the second line contains n integers (1..10⁹).

输出格式

Output a single integer, the answer.

样例 1

输入：

3
1 2 1

输出：

1

样例 2

输入：

3
1 2 3

输出：

1

样例 3

输入：

2
7 7

输出：

1

样例说明

Example 1: the six counts sorted are 1, 1, 1, 2, 2, 2; take the third one, 1.

Example 2: the six counts sorted are 1, 1, 1, 2, 2, 3; the answer is 1.

Example 3: every subarray contains only one value, so the answer is 1.