题目描述

定义一个长度为 $M$ 的序列的中位数为这个序列中第 $\lfloor\frac M 2\rfloor + 1$ 小的数。

现在有一个长度为 $N$ 的序列 $A$，将 $A$ 的所有子段的中位数取出来作为一个序列 $S$，问序列 $S$ 的中位数是多少。

说明/限制

$\begin{array}{l}1\le N\le 10^5\\1\le A_i\le 10^9\end{array}$

样例1解释

所有可能的子段为 $[10],[30],[20],[10,30],[30,20],[10,30,20]$，它们的中位数分别为 $10,30,20,30,30,20$，而 $[10,30,20,30,30,20]$ 的中位数为 $30$，因此答案为 $30$。