#include<cstdio>
int v[200001],f[200001],p,nr=-1;


int cautare(int x)
{
    for(int i=1;i<=p;++i)
        if(f[i]==x)
            return i;
}



void percolate(int nr)
{
    int aux,lim,q;
    lim=(nr+1)/2-1;
    while(v[nr]<v[lim]&&lim>=0)
    {
        aux=v[nr];
        v[nr]=v[lim];
        v[lim]=aux;
        q=cautare(nr);
        f[q]=lim;
        q=cautare(lim);
        f[q]=nr;
        nr=lim;
        lim=(nr+1)/2-1;
    }
    f[++p]=nr;
}



void inserare(int x)
{
    v[++nr]=x;
    percolate(nr);
}





void cernere(int n)
{
    int k,aux,min,q;
    do
    {
        k=n;
        min=v[k];
        if(v[2*n+1]<min)
        {
            min=v[2*n+1];
            k=2*n+1;
        }
        if(v[2*n+2]<min)
        {
            min=v[2*n+2];
            k=2*n+2;
        }
        aux=v[k];
        v[k]=v[n];
        v[n]=aux;
        q=cautare(k);
        f[q]=n;
        q=cautare(n);
        f[q]=k;
    }while(k!=n);
}




int main()
{
    freopen("heapuri.in","r",stdin);
    freopen("heapuri.out","w",stdout);
    int n,i,k,x;
    scanf("%d",&n);
    for(i=1;i<=n;++i)
    {
        scanf("%d",&k);
        if(k==1)
        {
            scanf("%d",&x);
            inserare(x);
        }
        else
            if(k==2)
            {
                scanf("%d",&x);
                v[f[x]]=v[nr-1];
                cernere(f[x]);
            }
            else
            {
                printf("%d\n",v[0]);
                v[0]=v[nr];
                cernere(0);
            }
    }
    return 0;
}