AT_arc101_b.[ABC107D] Median of Medians

长度为 $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\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 翻译