配点 : $700$ 点

問題文

長さ $M$ の数列 $b$ の 中央値 を次のように定義します。

• $b$ を昇順にソートして得られる数列を $b'$ とする。 このとき、$b'$ の $M / 2 + 1$ 番目の要素の値を、$b$ の中央値とする。 ここで、$/$ は小数点以下を切り捨てる除算である。

例えば、$(10, 30, 20)$ の中央値は $20$ であり、$(10, 30, 20, 40)$ の中央値は $30$ であり、$(10, 10, 10, 20, 30)$ の中央値は $10$ です。

すぬけ君は次のような問題を思いつきました。

長さ $N$ の数列 $a$ があります。 各 $(l, r)$ ($1 \leq l \leq r \leq N$) について、$a$ の連続部分列 $(a_l, a_{l + 1}, ..., a_r)$ の中央値を $m_{l, r}$ とします。 すべての $(l, r)$ に対する $m_{l, r}$ を並べ、新たに数列 $m$ を作ります。 $m$ の中央値を求めてください。

制約

• $1 \leq N \leq 10^5$
• $a_i$ は整数である。
• $1 \leq a_i \leq 10^9$

入力

入力は以下の形式で標準入力から与えられる。

$N$

$a_1$ $a_2$ $...$ $a_N$

出力

$m$ の中央値を出力せよ。

3
10 30 20

30

$a$ のそれぞれの連続部分列の中央値は次のようになります。

• $(10)$ の中央値は $10$
• $(30)$ の中央値は $30$
• $(20)$ の中央値は $20$
• $(10, 30)$ の中央値は $30$
• $(30, 20)$ の中央値は $30$
• $(10, 30, 20)$ の中央値は $20$

よって、$m = (10, 30, 20, 30, 30, 20)$ となり、$m$ の中央値は $30$ です。

1
10

10

10
5 9 5 9 8 9 3 5 4 3

8