/////////a[i]==pozitia in h a nr inserat al i-lea
/////////b[i]==al catelea e inserat in h nr al i-leaa
#include<stdio.h>
using namespace std;
int u,t,x,i,n,h[200003],a[200003],b[200003];
int swap(int k,int t)
{
	int x,a1,a2,b1,b2;
	x=h[t];
	h[t]=h[k];
	h[k]=x;
	a1=a[t];
	a2=a[k];
	b1=b[t];
	b2=b[k];
	b[k]=a2;
	b[t]=a1;
	a[k]=b2;
	a[t]=b1;
}
void heapup(int k)
{
	int t;
	if(k<=0) return ;
	else
	{
		t=k/2;
		if(h[t]>h[k])
		{	
			swap(k,t);
			heapup(t);
		}
	}
}
int heapdown(int poz)
{
	int p;
	swap(poz,u);
	h[poz]=h[u];
	h[u]=1000000005;
	u--;
	p=poz;
	if(h[p]>=h[p/2]&&h[p]<=h[p*2]&&h[p]<=h[p*2+1]) return 0;
	else
	{
		if(h[p]>=h[p/2])
		{
			if(h[p*2]<h[p*2+1]) t=p*2;
			else t=p*2+1;
			swap(t,p);
		}
		else swap(p,p/2);
	}
}
int main()
{
freopen("heapuri.in","r",stdin);
freopen("heapuri.out","w",stdout);
scanf("%d",&n);
for(i=1;i<=n;i++)
{
	scanf("%d",&t);
	if(t!=3) scanf("%d",&x);
	if(t==1)
	{
		u++;
		h[u]=x;
		b[u]=u;
		a[u]=u;
		heapup(u);
	}
	else
	if(t==2) heapdown(b[x]);
	else
	{
		printf("%d\n",h[1]);
		heapdown(1);
	}
}
return 0;
}