#include<bits/stdc++.h>
using namespace std;
struct jud {
	bool from;
	int lo;
	int num;
};
struct node {
	int size;
	int l;
	int r;
};
node tree[500000];
vector<jud> li;
int shoot[110005];
int ins[10005];
int fs[100005];
bool md[10005];
bool cmp(jud a,jud b) {
	return a.num<b.num;
}
void maketree(int l,int r,int lo) {
	tree[lo].l=l;
	tree[lo].r=r;
	tree[lo].size=0;
	if(l!=r) {
		int mid=(l+r)/2;
		maketree(l,mid,lo*2);
		maketree(mid+1,r,lo*2+1);
	}
}
int find(int num,int lo,int ji) {
	cout<<tree[lo].l<<" "<<tree[lo].r<<" "<<ji<<" "<<num<<endl;
	if(tree[lo].l==tree[lo].r) return tree[lo].l;
	if(tree[lo*2].size+ji<num) return find(num,lo*2+1,ji+tree[lo*2].size);
	else return find(num,lo*2,ji);
}
void in(int num,int lo) {
	tree[lo].size+=1;
	if(tree[lo].l==tree[lo].r) return;
	if(tree[lo*2].r>=num) in(num,lo*2);
	else in(num,lo*2+1);
}
int main() {
	int n,m;
	scanf("%d",&n);
	int ind=0;
	for(int i=1; i<=n; i++) {
		jud rua;
		rua.from=0;
		rua.lo=i;
		scanf("%d",&rua.num);
		li.push_back(rua);
	}
	scanf("%d",&m);
	for(int i=1; i<=m; i++) {
//		cout<<i<<endl;
		char rua[3];
		scanf("%s",&rua);
		if(rua[0]=='a') {
			jud rub;
			scanf("%d",&rub.num);
			rub.lo=i;
			rub.from=1;
			li.push_back(rub);
		} else md[i]=1;
	}
	sort(li.begin(),li.end(),cmp);
	for(int i=0; i<li.size(); i++) {
		int tian;
		if(i==0 || li[i].num>li[i-1].num) tian=++ind;
		else tian=ind;
		shoot[ind]=li[i].num;
		int lo=li[i].lo;
		if(li[i].from) ins[lo]=ind;
		else fs[lo]=ind;
	}
	for(int i=1;i<=n;i++) cout<<fs[i]<<' ';
	cout<<endl;
	for(int i=1;i<=m;i++) if(!md[i]) cout<<ins[i]<<" ";
	cout<<endl;
	maketree(1,ind,1);
	for(int i=1; i<=n; i++) in(fs[i],1);
	for(int i=1; i<=m; i++) {
		if(md[i]) {
			int out;
			if((tree[1].size)%2==1) out=find(tree[1].size/2+1,1,0);
			else out=min(find(tree[1].size/2,1,0),find(tree[1].size/2+1,1,0));
			printf("%d\n",shoot[out]);
		} else in(ins[i],1);
	}
	return 0;
}

线段树+离散化做的