中位数的中位数

题目描述

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

样例

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

数据范围

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