题目描述

给定一个由 $N$ 个元素组成的整数序列，现在有两种操作：

• add a：在该序列的最后添加一个整数 $a$，组成长度为 $N + 1$ 的整数序列。
• mid：输出当前序列的中位数。

中位数是指将一个序列按照从小到大排序后处在中间位置的数。（若序列长度为偶数，则指处在中间位置的两个数中较小的那个）

• 例 $1$：$\text{1 2 13 14 15 16}$ 中位数为 $13$。
• 例 $2$：$\text{1 3 5 7 10 11 17}$ 中位数为 $7$。
• 例 $3$：$\text{1 1 1 2 3}$ 中位数为 $1$。

输入格式

第一行为初始序列长度 $N$。

第二行为 $N$ 个整数，表示整数序列，数字之间用空格分隔。

第三行为操作数 $M$，即要进行 $M$ 次操作。

下面为 $M$ 行，每行输入格式如题意所述。

输出格式

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

6
1 2 13 14 15 16
5
add 5
add 3
mid
add 20
mid

5
13

提示

对于 $30\%$ 的数据，$1 \le N \le 10^4$，$0 \le M \le 10^3$。

对于 $100\%$ 的数据，$1 \le N \le 10^5$，$0 \le M \le 10^4$。

序列中整数的绝对值不超过 $10^9$，序列中的数可能有重复。