#include<stdio.h>
int a[500004],heap[500004],poz[500004],nr2,nr,ok,n;
void heap_up(int i)
{
    int aux;
    if (i>1)
        if (heap[i]>heap[i/2])
        {
            aux=heap[i];
            heap[i]=heap[i/2];
            heap[i/2]=aux;
            poz[heap[i]]=i;
            poz[heap[i/2]]=i/2;
            heap_up(i/2);
        }
}
void heap_down(int x)
{
    int aux, y = 0;
    while (x != y)
    {
        y=x;
        if(y*2<=nr&&a[heap[x]]>a[heap[y*2]])
        x=y*2;
        if(y*2+1<=nr&&a[heap[x]]>a[heap[y*2+1]])
        x=y*2+1;
        aux=heap[x];
        heap[x]=heap[y];
        heap[y]=aux;
        poz[heap[x]]=x;
        poz[heap[y]]=y;
    }
}
int main()
{
    int i,aux,val,x;
    freopen("heapuri.in","r",stdin);
    freopen("heapuri.out","w",stdout);
    scanf("%d",&n);
    nr2=n;
    for (i=1;i<=n;i++)
    {
        scanf("%d",&val);
        if (val<=2)
        {
            scanf("%d",&x);
            if (val==1)
            {
                nr++;
                nr2++;
                a[nr2]=x;
                poz[nr2]=nr;
                heap[nr]=nr2;
                heap_up(nr);
            }
            if (val==2)
            {
                a[x]=-1;
                heap_up(poz[x]);
                poz[heap[1]] = 0;
                heap[1]=heap[nr--];
                poz[heap[1]]=1;
                if (nr>1)
                    heap_down(1);
            }
        }
        else
            printf("%d\n",a[heap[1]]);
    }
    return 0;
}