3402 - 中位数

给定一个由 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。

第一行为初始序列长度 N。第二行为 N 个整数，表示整数序列，数字之间用空格分隔。第三行为操作数 M，即要进行 M 次操作。下面为 M 行，每行输入格式如题意所述。

对于每个 \verb!mid! 操作输出中位数的值。

• 对于 100\% 的数据，1 ≤ N ≤ 100,000，0 ≤ M ≤ 10,000。序列中整数的绝对值不超过 10^9，序列中的数可能有重复。

省选