using namespace std;
//前一半数存在大根堆中，剩下的数存在小根堆中
priority_queue<int> q;//前一半数 ，大根堆 
priority_queue<int,vector<int>,greater<int> > xgd;//后一半数,小根堆 
int n,m;
int L,R;
int a[200010];
void add(int x)
{
	if(x<=q.top())
	{
		if(L==R)
		{
			q.push(x);
			L++;
		}
		else 
		{
			R++;
			q.push(x);
			xgd.push(q.top());
			q.pop();
		}
	}
	else 
	{
		if(L==R)
		{
			xgd.push(x);
			L++;
			q.push(xgd.top());
			xgd.pop();
		}
		else 
		{
			R++;
			xgd.push(x);
		}
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	sort(a,a+n+1);
	L=(n+1)/2;
	R=n-L;
	for(int i=1;i<=L;i++)q.push(a[i]);
	for(int i=L+1;i<=n;i++)xgd.push(a[i]);
	cin>>m;
	for(int i=1;i<=m;i++)
	{
		string x;int y;
		cin>>x;
		if(x=="add")
		{
			cin>>y;
			add(y);
		}
		if(x=="mid")cout<<q.top()<<endl;
	}
	
	return 0;
}