#include<stdio.h>

int a[200005],poz[200005],nr[200005];


void ins(int siz,int i)
{
	int aux,aux2,fiu=0,tt=0,k=siz;
	do
	{
		tt=fiu=0;
		if(a[k>>1]>a[k])
		{
			poz[nr[k>>1]]=k;
			aux2=nr[k];
			nr[k]=nr[k>>1];
			aux=a[k>>1];
			a[k>>1]=a[k];
			a[k]=aux;
			poz[i]=k>>1;
			nr[k>>1]=aux2;
		}
		k=k/2;
		if(a[k]<a[k/2]&&k/2!=0)
			tt=1;
		if(tt==0)
		{
			if(k/2<=siz)
				fiu=k/2;
			if(k/2&&a[k/2+1]<a[fiu])
				fiu++;
			if(a[k]<=a[fiu])
				fiu=0;
		}
		if(fiu)
		{
			poz[nr[k>>1]]=k;
			aux2=nr[k];
			nr[k]=nr[fiu];
			aux=a[k];
			a[k]=a[fiu];
			a[fiu]=aux;
			poz[i]=fiu;
			nr[fiu]=aux2;
		}
	}while(tt||fiu);
}



int main()
{
	freopen("heapuri.in","r",stdin);
	freopen("heapuri.out","w",stdout);
	int n,siz=0,i,x,y;
	scanf("%d",&n);
	for(i=1;i<=n;++i)
	{
		scanf("%d",&x);
		if(x==3)
			printf("%d\n",a[1]);
		else
		{
			scanf("%d",&y);
			if(x==1)
			{
				a[++siz]=y;
				poz[siz]=siz;
				nr[siz]=siz;
				ins(siz,siz);
				
			}
			else
			{
				a[poz[y]]=a[siz];
				poz[nr[siz]]=poz[y];
				nr[poz[y]]=nr[siz];
				poz[y]=0;
				--siz;
				ins(siz,nr[siz+1]);
				nr[siz+1]=0;
			}
		}
	}
	return 0;
}