RT....貌似没有找到明显错误。

用的Treap。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cstdlib>
#include<ctime>
#include<cmath>
#include<iomanip>
#include<map>
using namespace std;
template<typename T>inline void read(T &x){//优化
	x=0;
	char ch=getchar();
	bool fl=0;
	while(ch<'0'||ch>'9') fl=(fl||ch=='-'),ch=getchar();
	while(ch<='9'&&ch>='0') x=x*10+(ch^'0'),ch=getchar();
	x=fl?-x:x;
}
template<typename T>void prt(T x){
	if(x>9) prt(x/10);
	putchar(x%10+'0');
}
template<typename T>inline void put(char ch,T x){
	if(x<0) putchar('-'),x=-x;
	prt(x);
	putchar(ch);
}
inline char getc(){
	char ch=getchar();
	while(ch!='a'&&ch!='m') ch=getchar();
	return ch;
}
#define N 150005
int root,cnt,n,m;
struct node{//lson左儿子，rson右儿子，val权值，num当前权值个数，siz子树大小，key维护堆
	int lson,rson,val,num,siz,key;
}t[N];
#define lc(X) t[X].lson
#define rc(X) t[X].rson
namespace Treap{
	inline void push_up(int x){//更新
		t[x].siz=t[lc(x)].siz+t[rc(x)].siz+t[x].num;
	}
	inline int make_node(int val){//新建结点
		t[++cnt].key=rand();
		t[cnt].num=t[cnt].siz=1;
		t[cnt].val=val;
		return cnt;
	}
	inline void lrotate(int &x){//旋转
		int k=rc(x);
		rc(x)=lc(k);
		lc(k)=x;
		t[k].siz=t[x].siz;
		push_up(x);
		x=k;
	}
	inline void rrotate(int &x){
		int k=lc(x);
		lc(x)=rc(k);
		rc(k)=x;
		t[k].siz=t[x].siz;
		push_up(x);
		x=k;
	} 
	void insert(int &x,int val){//插入
		if(!x) return x=make_node(val),void();
		t[x].siz++;
		if(t[x].val==val) t[x].num++;//直接维护
		else if(t[x].val>val){
			insert(lc(x),val);
			if(t[x].key>t[lc(x)].key) rrotate(x);//维护堆
		}else{
			insert(rc(x),val);
			if(t[x].key<t[rc(x)].key) lrotate(x);//维护堆
		}
	}
	int qnum(int x,int k){//x表示当前结点，k表示查询子树中第k小
		if(!x) return 0;//虽然没有必要...
		if(t[lc(x)].siz>=k) return qnum(lc(x),k);//在左子树
		if(t[x].num+t[lc(x)].siz<k) return qnum(rc(x),k-t[x].num-t[lc(x)].siz);//在又子树
		return t[x].val;//直接返回
	}
}
using namespace Treap;
int main(){
	srand(time(NULL));
	read(n);
	for(int i=1,x;i<=n;i++) read(x),insert(root,x);//插进去
	read(m);
	for(int i=1,x;i<=m;i++)
		if(getc()=='a') read(x),insert(root,x);//如果add就插进去
		else put('\n',qnum(root,(t[root].siz+1)>>1));//查询
		
	return 0;
}