题目描述

我们定义一个序列 $b$ 的中位数如下：

• 设 $b′$ 是将 $b$ 按非降序排列得到的序列，那么 $b$ 的第 $M/2+1$ 个元素就是 $b$ 的中位数。这里的 / 表示整数除法（向下取整）。

例如，(10,30,20) 的中位数是 20；(10,30,20,40) 的中位数是 30；(10,10,10,20,30) 的中位数是 10。

Snuke 提出了以下问题。

给定长度为 $N$ 的序列 $a$。 对于每对$(l,r)$，设 $m_{l,r}$ 是子序列$a_l,a_{l+1}...a_{r}$ 的中位数。 我们将列出所有 $(l,r)$ 对应的 $m_{l,r}$，得到一个新的序列 $m$。 求 $m$ 的中位数。

输入

输入以以下格式从标准输入中给出：

$N$

$a_1 a_2 ...a_N$

输出

输出 $m$ 的中位数。

3
10 30 20

30

【样例1解释】 每个子序列的中位数如下：

• (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

提示

• $1 \leq N \leq 10^5$
• $a_i$ 是一个整数。
• $1 \leq a_i \leq 10^9$