#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
//#include<>
const int MAXN=1e6+10;
int q[2][MAXN];
int main(){
	int n,m;
	int now=1,pre=0;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		int a;
		scanf("%d",&a);
		q[pre][i]=a;
	}	
	std::sort(q[pre]+1,q[pre]+n+1);
	int cnt=n;
	scanf("%d",&m);
	for(int i=1;i<=m;i++)
	{
		char ch[3];
		scanf("%s",ch);
		if(ch[0]=='a')
		{
			int a,ind;
			scanf("%d",&a);
			for(int i=1;i<=cnt;i++)
			{
				if(q[pre][i]>=a)
				{
					ind=i;
					break;
				}
				q[now][i]=q[pre][i];
				if(i==cnt)
					ind=cnt+1;
			}
			cnt++;
			q[now][ind]=a;
			for(int i=ind+1;i<=cnt;i++)
			{
				q[now][i]=q[pre][i-1];
			}
			std::swap(now,pre);
//			for(int i=1;i<=cnt;i++)
//				printf("%d ",q[pre][i]);
//			printf("\n");			
		}
		else 
		{
			int k=cnt/2;
			if(cnt%2==1)
				k++;
			printf("%d\n",q[pre][k]);
		}
	}
	return 0;
}