题目描述

我们将长度为$M$的序列$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)$（$1 \leq l \leq r \leq N$），令$m_{l, r}$ 是由$a$的连续子序列$(a_l, a_{l + 1}, ..., a_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$的中位数。

示例输入 1

3
10 30 20

示例输出 1

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$。

示例输入 2

1
10

示例输出 2

10

示例输入 3

10
5 9 5 9 8 9 3 5 4 3

示例输出 3

8