#include<bits/stdc++.h>
using namespace std;
const int N=1e6+100;
int n,v[N],cnt[N],sz[N],tot,h[N],q,root,ls[N],rs[N];
void szup(int x){
	sz[x]=sz[ls[x]]+sz[rs[x]]+cnt[x];
}
void fl(int rt,int &l,int &r,int x){
	if(!rt){
		l=r=0;
		return ;
	}
	if(v[rt]<=x){
		l=rt;
		fl(rs[rt],rs[l],r,x);
		szup(l);
	}
	else{
		r=rt;
		fl(ls[rt],l,ls[r],x);
		szup(r);
	}
}
void pmfl(int rt,int &l,int &r,int x){
	if(!rt){
		l=r=0;
		return ;
	}
	int s=sz[ls[rt]]+1;
	if(s<=x){
		l=rt;
		pmfl(rs[rt],rs[l],r,x-s+1-cnt[rt]);
		szup(l);
	}
	else{
		r=rt;
		pmfl(ls[rt],l,ls[r],x);
		szup(r);
	}
}
int hb(int l,int r){
	if(!l || !r)	return l+r;
	if(h[l]<h[r]){
		rs[l]=hb(rs[l],r);
		szup(l);
		return l;
	}
	else{
		ls[r]=hb(l,ls[r]);
		szup(r);
		return r;
	}
}
void jd(int x){
	if(!root){
		tot++;
		cnt[tot]=sz[tot]=1;
		h[tot]=rand();
		v[tot]=x;
		root=tot;
		return ;
	}
	int l,r,i;
	fl(root,l,r,x);
	fl(l,l,i,x-1);
	if(cnt[i]){
		cnt[i]++;
		szup(i);
	}
	else{
		tot++;
		cnt[tot]=sz[tot]=1;
		h[tot]=rand();
		v[tot]=x;
	}
	root=hb(root,tot);
	hb(hb(l,i),r);
}
int pms(int x){
	int l,r,s;
	pmfl(root,l,r,x-1);
	pmfl(r,r,s,1);
	int ans=v[r];
	hb(l,hb(r,s));
	return ans;
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		int v;
		cin>>v;
		jd(v);
	}
	cin>>q;
	while(q--){
		string op;
		int x;
		cin>>op;
		if(op[0]=='a'){
			n++;
			cin>>x;
			jd(x);
		}
		else
			cout<<pms((n+1)/2)<<endl;
	}
	return 0;
}