rt

#include<cstdio>
#include<algorithm>
#define it long long
using namespace std;
it heap[1000005],uheap[1000005],num,k,lo,len,len1,w;
char op[10];
void sk(it A[],it b)
{
	printf("\n");
	for(int a=1;a<=b;a++) printf("%d ",A[a]);
	printf("\n");
}
void heaped(it A[],it n)
{
	it k=1,o;
	while(k*2<=n)
	{
		o=k;
		k*=2;
		k+=(A[k]>A[k+1])&(k<n);
		if(A[o]>A[k])
		{
			swap(A[o],A[k]);
		}
		else break;
	}
}
void unheaped(it A[],it n)
{
	it k=n,o;
	while(k/2>=1)
	{
		o=k;
		k/=2;
		if(!o%2)o+=(A[o]>A[o+1])&(o<n);
		if(A[o]<A[k])
		{
			swap(A[o],A[k]);
		}
		else break;
	}
}
void uheaped(it A[],it n)
{
	it k=1,o;
	while(k*2<=n)
	{
		o=k;
		k*=2;
		k+=(A[k]<A[k+1])&(k<n);
		if(A[o]<A[k])
		{
			swap(A[o],A[k]);
		}
		else break;
	}
}
void uunheaped(it A[],it n)
{
	it k=n,o;
	while(k/2>=1)
	{
		o=k;
		k/=2;
		if(!o%2)o+=(A[o]<A[o+1])&(o<n);
		if(A[o]>A[k])
		{
			swap(A[o],A[k]);
		}
		else break;
	}
}
int main()
{
	scanf("%lld",&num);
	for(int a=1;a<=num;a++)//heap小根堆,uheap大根堆 
	{
		scanf("%lld",&lo);
		uheap[++len1]=lo;
		uunheaped(uheap,len1);
	} 
	int t=len1;
	for(int a=1;a<=num/2+(num%2==1);a++)
	{
		heap[++len]=uheap[1];
		swap(uheap[1],uheap[len1--]);
		uheaped(uheap,len1);
		unheaped(heap,len);
	}
	scanf("%lld",&w);
	for(it a=1;a<=w;a++)
	{
		scanf("%s",&op);
		if(op[0]=='a')
		{
			scanf("%lld",&lo);
			num++;
			uheap[++len1]=lo;
			uunheaped(uheap,len1);
	    }
		else
		{
			if(num%2==1)printf("%lld\n",heap[1]);
			else if(uheap[1]==0) printf("%lld\n",heap[1]);
			else if(heap[1]==0) printf("%lld\n",uheap[1]);
			else printf("%lld\n",min(uheap[1],heap[1]));

		}
		while(len>num/2+(num%2==1))
		{
			uheap[++len1]=heap[1];
			uunheaped(uheap,len1);
			heap[1]=heap[len--];
			heaped(heap,len);
//		printf("len:%d;len1:%d num:%d\n",len,len1,num);
		}
		while(len<num/2+(num%2==1))
		{
			heap[++len]=uheap[1];
			unheaped(heap,len);
			uheap[1]=uheap[len1--];
			uheaped(uheap,len1);
		}
	}
	return 0;
}
/*
5
2 3 5 1 4


*/