P3871 [TJOI2010] 中位数

给定一个由 $N$ 个元素组成的整数序列，现在有两种操作： - $\texttt{1 add }\textit{a}$：在该序列的最后添加一个整数 $a$，组成长度为 $N + 1$ 的整数序列。 - $\texttt{2 mid}$：输出当前序列的中位数。 中位数是指将一个序列按照从小到大排序后处在中间位置的数。（若序列长度为偶数，则指处在中间位置的两个数中较小的那个） 例 $1$：$[1, 2, 13, 14, 15, 16]$ 中位数为 $13$。 例 $2$：$[1, 3, 5, 7, 10, 11, 17]$ 中位数为 $7$。 例 $3$：$[1, 1, 1, 2, 3]$ 中位数为 $1$。

无

无

### 数据范围及约定 - 对于 $30\%$ 的数据，$1 ≤ N ≤ 10,000$，$0 ≤ M ≤ 1,000$。 - 对于 $100\%$ 的数据，$1 ≤ N ≤ 100,000$，$0 ≤ M ≤ 10,000$。 序列中整数的绝对值不超过 $10^9$，序列中的数可能有重复。