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 翻译