[TJOI2010]中位数

题目描述

给定一个由N个元素组成的整数序列,现在有两种操作: 1 add a 在该序列的最后添加一个整数a,组成长度为N + 1的整数序列 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行,每行输入格式如题意所述。

输出格式


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

输入输出样例

输入样例 #1

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

输出样例 #1

5
13

说明

对于30%的数据,1 ≤ N ≤ 10,000,0 ≤ M ≤ 1,000 对于100%的数据,1 ≤ N ≤ 100,000,0 ≤ M ≤ 10,000 序列中整数的绝对值不超过1,000,000,000,序列中的数可能有重复 每个测试点时限1秒