#include<fstream>
using namespace std;
long h[200005],var,poz[200005];
int i,a,b,n,l,m,p;
void sus(int pz)
{
	int k=pz;
		while(h[k/2]<h[k]&&k>1)
		{
			var=h[k/2];
			h[k/2]=h[k];
			h[k]=var;
			k=k/2;
		}
	
}
void jos(int pz)
{
	int k,pozfiu;
	k=pz;
	do
	{
		pozfiu=0;
		if(2*k<=l)
		{
			pozfiu=2*k;
			if((2*k)+1<=l&&h[(2*k)+1]>h[2*k])
				pozfiu=(2*k)+1;
			if(h[pozfiu]<=h[k])
				pozfiu=0;
		}
		if(pozfiu!=0)
		{
			var=h[pozfiu];
			h[pozfiu]=h[k];
			h[k]=var;
			k=pozfiu;
		}
		
	}while(pozfiu!=0);
}
int cautare()
{
	int j;
	for(j=1;j<=l;j++)
			if(h[j]==poz[b])
				return j;
}
void eliminare()
{
	h[p]=h[l];
	l--;
	if(p>1&&h[p]>h[p/2])
		sus(p);
	else
        jos(p);
}

int main()
{
	ifstream fin("heapuri.in");
	fin>>n;
	ofstream fout("heapuri.out");
	for(i=1;i<=n;i++)
	{
		fin>>a;
		if(a==1)
			{
				fin>>b;
				h[++l]=b;
				poz[++m]=b;
				if(h[l/2]<h[l])
					sus(l);
		    }
		if(a==3)
		{
			if(l%2==0)
				fout<<h[l]<<endl;
			else
				if(h[l]<=h[l-1])
					fout<<h[l]<<endl;
				else
					fout<<h[l-1]<<endl;
		}
		if(a==2)
		{
			fin>>b;
			p=cautare();
			eliminare();
		}
	}
	fin.close();
	fout<<'\n';
	fout.close();
	return 0;
}