RT，样例过了，自己整了几组数据运行结果也都是对的，不知道哪里写错了。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=100005;
struct Node{
	ll ch[2];
	ll f,val,cnt,son;
}t[N*4];
ll n,root,tot,k;
void push_up(ll x){
	t[x].son=t[t[x].ch[0]].son+t[t[x].ch[1]].son+t[x].cnt;
}
void rotate(ll x){
	ll y=t[x].f;
	ll z=t[y].f;
	ll k=(t[y].ch[1]==x);
	t[z].ch[t[z].ch[1]==y]=x;t[x].f=z;
	t[y].ch[k]=t[x].ch[k^1];t[t[x].ch[k^1]].f=y;
	t[x].ch[k^1]=y;t[y].f=x;
	push_up(y);push_up(x);
}
void Splay(ll x,ll goal){
	while(t[x].f!=goal){
		ll y=t[x].f;
		ll z=t[y].f;
		if(z!=goal){
			(t[z].ch[0]==y)^(t[y].ch[0]==x)?rotate(x):rotate(y);
		}
		rotate(x);
	}
	if(goal==0){
		root=x;
	}
}
void insert(ll x){
	ll u=root,ff=0;
	while(u&&t[u].val!=x){
		ff=u;
		u=t[u].ch[t[u].val<x];
	}
	if(u){
		t[u].cnt++;
	}
	else{
		u=++tot;
		if(ff){
			t[ff].ch[t[ff].val<x]=u;
		}
		t[u].son=t[u].cnt=1;t[u].f=ff;t[u].val=x;
	}
	Splay(u,0);
}
ll rk(ll x){
	ll u=root;
	if(t[u].son<x)return false;
	while(1){
		ll y=t[u].ch[0];
		if(x>t[y].son+t[u].cnt){
			x=x-t[y].son-t[u].cnt;
			u=t[u].ch[1];
		}
		else if(t[y].son>=x){
			u=y;
		}
		else{
			Splay(u,0);
			return t[u].val;
		}
	}
}
int main(){
	scanf("%lld",&n);
	insert(-1145141999);
	insert(1145141999);
	for(int i=1;i<=n;i++){
		ll aaa;scanf("%lld",&aaa);
		insert(aaa);
	}
	scanf("%lld",&k);
	for(int i=1;i<=k;i++){
		string s;cin>>s;
		if(s=="add"){
			ll x;scanf("%lld",&x);insert(x);
		}
		else{
			ll k;
			k=(tot-1)/2;
			printf("%lld\n",rk(k+1));
		}
	}
	return 0;
}