#include<cstdio>
#include<algorithm>
using namespace std;
FILE*in=fopen("heapuri.in","r");
FILE*out=fopen("heapuri.out","w");
int n,i,v[200003],ct=0,a,ver[200003],b,l,ctt=0,k,x,lp;
int main()
{
    fscanf(in,"%d",&n);
    for(i=1;i<=n;i++)
    {
        ver[i]=i;
    }
    for(i=1;i<=n;i++)
    {
        fscanf(in,"%d",&a);
        if(a==1)
        {
            ct++;
            fscanf(in,"%d",&v[ct]);
            k=ct;
            while(v[k]<v[k/2])
            {
                swap(v[k],v[k/2]);
                swap(ver[k],ver[k/2]);
                k=k/2;
            }
        }
        if(a==2)
        {
            fscanf(in,"%d",&b);
            x=1;
            while(ver[x]!=b)
            {
                x++;
            }
            swap(v[ct],v[x]);
            swap(ver[ct],ver[x]);
            v[ct]=0;
            ct--;
            k=x;
            l=x;
            while(v[k]<v[k/2])
            {
                swap(v[k],v[k/2]);
                swap(ver[k],ver[k/2]);
                k=k/2;
            }
            while((v[l]>v[2*l]||v[l]>v[2*l+1])&&l<=ct/2)
            {
                lp=l;
                if(v[2*l]<=v[2*l+1])
                {
                    swap(v[l],v[2*l]);
                    swap(ver[l],ver[2*l]);
                    l=2*l;
                }
                if(v[2*lp]>v[2*lp+1]&&ct>=2*lp+1)
                {
                    swap(v[lp],v[2*lp+1]);
                    swap(ver[lp],ver[2*lp+1]);
                    l=2*l+1;
                }
                if(2*lp+1>ct)
                {
                    if(v[lp]>v[2*lp])
                    {
                        swap(v[l],v[2*l]);
                        swap(ver[l],ver[2*l]);
                    }
                    break;
                }
            }
        }
        if(a==3)
        {
            fprintf(out,"%d\n",v[1]);
        }
    }
}