#include<fstream>

using namespace std;

ifstream f("heapuri.in");
ofstream g("heapuri.out");

const int maxn=200005;

int a[maxn],h[maxn],pos[maxn],i,n,x,y,k,p;

void push(int p)
{
    int aux;
    while(x.2&&a[h[x]]<a[h[x/2]])
    {
        aux=h[x];
        h[x]=h[x/2];
        h[x/2]=aux;
        pos[h[x]]=x;
        pos[h[x/2]]=x/2;
        x/=2;
    }
}

void pop(int x)
{
    int aux,t=0;
    while(x!=t)
    {
        t=x;
        if(t*2<=p&&a[h[x]]>a[h[t<<1]])
            t*=2;
        if(t*2+1<=p&&a[h[x]]>a[h[t*2+1]])
            t=t*2+1;
        aux=h[x];
        h[x]=h[t];
        h[t]=aux;
        pos[h[t]]=t;
        pos[h[x]]=x;
    }
}

int main()
{
    f>>n;
    for(i=1;i<=n;++i)
    {
        f>>x;
        if(x<3)
            f>>y;
        if(x==1)
        {
           a[++k]=y;
           h[++p]=k;
           pos[k]=p;
           push(p);
        }
        else if(x==2)
        {
            a[y]=-1;
            push(pos[y]);
            pos[h[1]]=0;
            h[1]=h[p--];
            if(p>1)
                pop(1);
        }

        else g<<a[h[1]]<<"\n";
    }

    f.close();
    g.close();

    return 0;
}