#include<stdio.h>
long h[200010],v[200010],poz[200010];
long aux,n,i,j,k,x,a;

void up(long i)
{
	if(v[0]==1)
		return;
	while(i>1)
	{
		if(v[h[i]]<v[h[i/2]])
		{
			aux=poz[h[i]];poz[h[i]]=poz[h[i/2]];poz[h[i/2]]=aux;
			aux=h[i];h[i]=h[i/2];h[i/2]=aux;
			i=i/2;
		}
		else return;
	}
}

void down()
{
	while(1)
	{
		if(j*2>h[0]) return;
		if(v[h[j*2]]<v[h[j*2+1]])
		{
			aux=poz[h[j]];poz[h[j]]=poz[h[j*2]];poz[h[j*2]]=aux;
			aux=h[j];h[j]=h[j*2];h[j*2]=aux; 
			j=j*2;
		}
		else
		{
			if(j*2+1>h[0]) return;
			aux=poz[h[j]];poz[h[j]]=poz[h[j*2+1]];poz[h[j*2+1]]=aux;
			aux=h[j];h[j]=h[j*2+1];h[j*2+1]=aux; 
			j=j*2+1;
		}
	}
}

int main()
{
	freopen("heapuri.in","r",stdin);
	freopen("heapuri.out","w",stdout);
	scanf("%ld",&n);
	for(i=1;i<=n;++i)
	{
		scanf("%d",&x);
		if(x<3) 
		{
			scanf("%ld",&a);
			if(x==1)
			{
				v[0]++;v[v[0]]=a;
				h[++h[0]]=v[0];
				poz[v[0]]=h[0];
				up(h[0]);
			}
			else
			{
				j=poz[a];
				down();
				aux=poz[h[j]];poz[h[j]]=poz[h[h[0]]];poz[h[h[0]]]=aux;
				aux=h[j];h[j]=h[h[0]];h[h[0]]=aux; 
				h[h[0]]=poz[a]=0;
				h[0]--; 
				if(j!=h[0]+1) up(j);
			}
		}
		else
			printf("%ld\n",v[h[1]]);
	}
	return 0;
}