#include<bits/stdc++.h>
#define ll long long
using namespace std;
inline int read()
{
	int x=0,f=1;char c=getchar();
	while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
	while(isdigit(c)){x=x*10+c-48;c=getchar();}
	return x*f;
}
inline void write(int x)
{
	if(x>9)write(x/10);
	putchar(x%10+48);
}
const int Max=1e5+100;
int n,m,now,t;
priority_queue<int> ma;
priority_queue<int,vector<int>,greater<int>> mi;
void down()
{
	if(mi.size()>now) {
		ma.push(mi.top());
		mi.pop();
	}
	if(mi.size()<now) {
		mi.push(ma.top());
		ma.pop();
	}
}
void push(int x)
{
	if(x>ma.top())mi.push(x);
	else ma.push(x);
	down();
}
int main()
{
	n=read();
	ma.push(0);
	for(int i=1;i<=n;i++) {
		int k;k=read();
		now=i/2;
		if(i%2==1)now++;
		push(k);
	}
	t=n;
	m=read();
	for(int i=1;i<=m;i++) {
		string s;
		cin>>s;
		if(s=="add") {
			int k;k=read();
			t++;
			now=t/2;
			if(t%2==1)now++;
			push(k);
		}
		else if(t%2==1)cout<<mi.top()<<endl;
		else cout<<ma.top()<<endl;
	}
	return 0;
}