#include<cstdio>

using namespace std;
int n,i,j,k,h[200010],val,lh,ord[200010],ordin,nor,poz[200010];
void read(),solve(),percolate(int ic),sift(int ic,int nc),sw(int i1,int i2);
int main()
{
	read();
	solve();
	return 0;
}
void read()
{
	freopen("heapuri.in","rt",stdin);
	freopen("heapuri.out","wt",stdout);
	scanf("%d",&n);
}
void solve()
{
	for(i=1;i<=n;i++)
	{ 
		scanf("%d",&k);
		if(k==3)
		{
			printf("%d\n",h[1]);
			continue;
		}
		if(k==1)
		{
			scanf("%d",&val);
			h[++lh]=val;
			ord[lh]=++ordin;
			poz[ordin]=lh;
			percolate(lh);
			continue;
		}
		scanf("%d",&nor);
		j=poz[nor];
		sw(j,lh);
		lh--;
		percolate(j);
		sift(j,lh);
	}
}
void sw(int i1,int i2)
{
	int aux;
	aux=h[i1];
	h[i1]=h[i2];
	h[i2]=aux;
	aux=ord[i1];
	ord[i1]=ord[i2];
	ord[i2]=aux;
	poz[ord[i1]]=i1;
	poz[ord[i2]]=i2;
}
void percolate(int ic)
{
	int is=ic>>1;
	if(is&&h[is]>h[ic])
	{
		sw(is,ic);
		percolate(is);
	}
}
void sift(int ic,int nc)
{
	int is=ic<<1;
	if(is>nc)
		return;
	if(is<nc)
		if(h[is+1]<h[is])
			is++;
	if(h[is]<h[ic])
	{
		sw(is,ic);
		sift(is,nc);
	}
}