#include<stdio.h>
long n,nr,h[200010],v[200010],poz[200010];
void coboara(long temp)
{
long aux,nm=nr/2,fiu1,fiu2;
while(temp<=nm)
{
	fiu1=temp*2;
	fiu2=temp*2+1;
	if(fiu2<=nr)
	{
		if (v[fiu1]<=v[fiu2] && v[fiu1]<v[temp])
		{
				aux=v[fiu1];
				v[fiu1]=v[temp];
				v[temp]=aux;
				aux=h[poz[fiu1]];
				h[poz[fiu1]]=h[poz[temp]];
				h[poz[temp]]=aux;
				aux=poz[fiu1];
				poz[fiu1]=poz[temp];
				poz[temp]=aux;
				temp=fiu1;
		}
		else if (v[fiu2]<=v[fiu1] && v[fiu2]<v[temp])
		{
				aux=v[fiu2];
				v[fiu2]=v[temp];
				v[temp]=aux;
				aux=h[poz[fiu2]];
				h[poz[fiu2]]=h[poz[temp]];
				h[poz[temp]]=aux;
				aux=poz[fiu2];
				poz[fiu2]=poz[temp];
				poz[temp]=aux;
				temp=fiu2;
		}
		else break;
	}
	else if (v[fiu1]<v[temp])
	{
				aux=v[fiu1];
				v[fiu1]=v[temp];
				v[temp]=aux;
				aux=h[poz[fiu1]];
				h[poz[fiu1]]=h[poz[temp]];
				h[poz[temp]]=aux;
				aux=poz[fiu1];
				poz[fiu1]=poz[temp];
				poz[temp]=aux;
				temp=fiu1;	
	}
	else break;
}
}
void urca(long temp)
{
long aux,tata;
while(temp>=2)
{
tata=temp/2;
if (v[temp]<v[tata])
{
	aux=v[temp];
	v[temp]=v[tata];
	v[tata]=aux;
	aux=h[poz[temp]];
	h[poz[temp]]=h[poz[tata]];
	h[poz[tata]]=aux;
	aux=poz[temp];
	poz[temp]=poz[tata];
	poz[tata]=aux;
	temp=tata;
}
else break;
}
coboara(temp);
}
int main()
{
long temp,i,x=0;
int t;
freopen("heapuri.in","r",stdin);
freopen("heapuri.out","w",stdout);
scanf("%ld",&n);
 for (i=1;i<=n;++i)
{
	scanf("%d",&t);
	if (t==1)
	{
			scanf("%ld",&temp);
			v[++nr]=temp;
			h[++x]=nr;
			poz[nr]=x;
			urca(nr);
	}
	else if (t==2)
	{
			scanf("%ld",&temp);
			v[h[temp]]=v[nr];
			h[poz[nr]]=h[temp];
			poz[h[temp]]=poz[nr];
			--nr;
			urca(h[temp]);
	}
	else
	{
		printf("%ld\n",v[1]);
	}
}
return 0;
}