#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
struct node{
	int ls, rs;
	int si, pri, key;
}t[N];
int cnt, root;
int n, m;
void pushup(int u) {
	t[u].si = t[t[u].ls].si + t[t[u].rs].si + 1;
}
int merge(int l, int r) {
	if(l == 0 or r == 0) 
		return l + r;
	if(t[l].pri > t[r].pri) {
		t[l].rs = merge(t[l].rs, r);
		pushup(l);
		return l;
	}
	else {
		t[r].ls = merge(l, t[r].ls);
		pushup(r);
		return r;
	}
}
void build(int x) {
	t[++cnt].si = 1;
	t[cnt].ls = t[cnt].rs = 0;
	t[cnt].pri = rand();
	t[cnt].key = x;
}
void split(int u, int x, int &l, int &r) {
	if(u == 0) {
		l = r = 0;
		return;
	}
	if(t[u].key <= x) {
		l = u;
		split(t[u].rs, x, t[u].rs, r);
	}
	else {
		r = u;
		split(t[u].ls, x, l, t[u].ls);
	}
	pushup(u);
}
int kth(int u, int k) {
	if(k == t[t[u].ls].si + 1) return u;
	if(k <= t[t[u].ls].si) return kth(t[u].ls, k);
	if(k > t[t[u].ls].si) return kth(t[u].rs, k - t[t[u].ls].si - 1);
}
void Insert(int x) {
	int l, r;
	split(root, x, l, r);
	build(x);
	root = merge(merge(l, cnt), r);
}
int op;
char c[3];
int a;
int main() {
	std::ios::sync_with_stdio(0);
	srand(time(NULL));
	cin>>n;
	for(int i = 1; i <= n; i++) {
		cin>>op;
		Insert(op);
	}
	cin>>m;
	while(m--) {
		cin>>c;
		if(c[0] == 'a') {
			cin>>a;
			Insert(a);
			++n;
		}
		else {
			int mid = (n + 1) / 2;
			cout<<t[kth(root, mid)].key<<'\n';
		}
	}
	return 0;
}