#include<stdio.h>
int v[200000],t[200000],j,x,n,op,poz[200000],y,c;
void schimba(int k1,int k2)
{
	int aux;
	aux=t[k1];
	t[k1]=t[k2];
	t[k2]=aux;
	poz[t[k1]]=k1;
	poz[t[k2]]=k2;
	aux=v[k1];
	v[k1]=v[k2];
	v[k2]=aux;
}
int fs(int k)
{
	return 2*k;
}
int fd(int k)
{
	return 2*k+1;
}
int p(int k)
{
	return k/2;
}
void urca_heap(int k)
{
	int aux;
	while(v[k]<v[p(k)]&&k>1)
	{
		aux=v[k];
		v[k]=v[p(k)];
		v[p(k)]=aux;
		
		aux=t[k];
		t[k]=t[p(k)];
		t[p(k)]=aux;
		poz[t[p(k)]]=p(k);
		poz[t[k]]=k;
		k=p(k);
	}
}
void coboara_heap(int k)
{
	int aux;
	while(v[k]>v[fs(k)]||v[k]>v[fd(k)])
	{
		if(v[fs(k)]>v[fd(k)]&&fd(k)<=j)
		{
		aux=v[k];
		v[k]=v[fd(k)];
		v[fd(k)]=aux;
		
		aux=t[k];
		t[k]=t[fd(k)];
		t[fd(k)]=aux;

		poz[t[k]]=k;
		poz[t[fd(k)]]=fd(k);
		
		k=fd(k);

		}
		else
		if(fs(k)<=j)
		{
		aux=v[k];
		v[k]=v[fs(k)];
		v[fs(k)]=aux;
		
		aux=t[k];
		t[k]=t[fs(k)];
		t[fs(k)]=aux;
		
		poz[t[k]]=k;
		poz[t[fd(k)]]=fd(k);
		
		k=fs(k);
		}
		else
			break;
	}
}					
int main ()
{
	freopen("heapuri.in","r",stdin);
	freopen("heapuri.out","w",stdout);
	scanf("%d",&n);
 	for(int i=1;i<=n;++i)
	{
		scanf("%d",&op);
		if(op!=3)
		{
			if(op==1)
			{
			++j;
			++y;
			scanf("%d",&x);
			v[j]=x;
			t[j]=y;	
			poz[y]=j;
			urca_heap(j);
			}
			else
				if(op==2)
				{
					scanf("%d",&x);
					c=poz[x];
					schimba(poz[x],j);
					v[j]=0;
					--j;
					if(c<=j)
					if(v[c]<v[p(c)])
						urca_heap(c);
					else
						if(v[c]>v[fs(c)]&&c*2<=j)
							coboara_heap(c);
						else
							if(v[c]>v[fd(c)]&&c*2+1<=j)
								coboara_heap(c);
					poz[x]=0;
				}
		}
		else
			printf("%d\n",v[1]);
	}
	return 0;
}