D - 中位数的中位数

得分：700分

问题描述

我们定义一个序列 $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_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$ 的中位数。

3
10 30 20

30

每个子序列的中位数如下：

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