Score : 700 points
We will define the median of a sequence b of length M, as follows:
For example, the median of (10, 30, 20) is 20; the median of (10, 30, 20, 40) is 30; the median of (10, 10, 10, 20, 30) is 10.
Snuke comes up with the following problem.
You are given a sequence a of length N. For each pair (l, r) (1 \leq l \leq r \leq N), let m_{l, r} be the median of the contiguous subsequence (a_l, a_{l + 1}, ..., a_r) of a. We will list m_{l, r} for all pairs (l, r) to create a new sequence m. Find the median of m.
Input is given from Standard Input in the following format:
N a_1 a_2 ... a_N
Print the median of m.
3 10 30 20
30
The median of each contiguous subsequence of a is as follows:
Thus, m = (10, 30, 20, 30, 30, 20) and the median of m is 30.
1 10
10
10 5 9 5 9 8 9 3 5 4 3
8