题目描述

长度为 $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$ 的中位数。

输入格式

输入以如下格式从标准输入给出。

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

输出格式

输出 $m$ 的中位数。

样例 1

输入

3
10 30 20

输出

30

样例 2

输入

1
10

输出

10

样例 3

输入

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$

样例解释 1

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

由 ChatGPT 4.1 翻译