Find Median of Subarray Uniqueness

For every non-empty contiguous subarray, compute its number of distinct values, and sort all these numbers; when their count is even, take the smaller of the two middle numbers. Find this lower median.

输入格式

The first line contains n and the second line contains n numbers. The complete original bounds are in the body: 1≤n≤100000, 1≤a[i]≤n; they are not overridden by the N/A placeholder at the end.

输出格式

Output a single integer, the answer.

样例 1

输入：

2
1 1

输出：

1

样例 2

输入：

3
1 2 3

输出：

1

样例 3

输入：

3
1 2 1

输出：

1

样例说明

The outputs of the three public examples are 1; 1; and 1, checked by independent enumeration or direct simulation.