#include<fstream>
#define minim(a,b) a<b?a:b
#define inf (1<<30)
using namespace std;
ifstream f("heapuri.in");
ofstream g("heapuri.out");
int n,i,k,v[200005],poz[200005];
void up(int k)
{
	if(k/2)
        if(v[k]<v[k/2])
        {
            swap(v[k],v[k/2]);
            swap(poz[k],poz[k/2]);
            k/=2;
            up(k);
        }
}
void down(int k)
{
    if(k<=i)
    {
        if(v[k]>v[2*k] && v[k]>v[2*k+1])
        {
            if(v[2*k]<v[2*k+1])
            {
                swap(v[k],v[2*k]);
                swap(poz[k],poz[2*k]);
                k=2*k;
                down(k);
            }
            else
            {
                swap(v[k],v[2*k+1]);
                swap(poz[k],poz[2*k+1]);
                k=2*k+1;
                down(k);
            }
        }
        else
        {
            if(v[k]>v[2*k])
            {
                swap(v[k],v[2*k]);
                swap(poz[k],poz[2*k]);
                k=2*k;
                down(k);
            }
            else
                if(v[k]>v[2*k+1])
                {
                    swap(v[k],v[2*k+1]);
                    swap(poz[k],poz[2*k+1]);
                    k=2*k+1;
                    down(k);
                }
        }
    }
}
int main()
{
	f>>n;
	int k=0;
	while(n--)
	{
		int x;
		f>>x;
		if(x==3)
			g<<v[1]<<'\n';
		else
		{
			if(x==1)
			{
				f>>v[++i];
				poz[++k]=k;
			}
			else
			{
				f>>x;
				v[poz[x]]=v[i];
				poz[i]=poz[x];
				v[i]=inf;
				i--;
				if(v[poz[x]]<v[poz[x]/2])
					up(poz[x]);
				else
					if(v[poz[x]]>v[2*poz[x]])
						down(poz[x]);
			}
		}
	}
	f.close();
	g.close();
	return 0;
}