#include <stdio.h>
#define DIM 200005

int a[DIM],h[DIM],poz[DIM];
int n,m,l;

void swap (int &a,int &b)
{
    int aux=a;
    a=b;
    b=aux;
}

void upheap (int nod)
{
    for (; nod>1 && a[h[nod]]<a[h[nod/2]]; nod/=2)
    {
        swap (poz[h[nod]],poz[h[nod/2]]);
        swap (h[nod],h[nod/2]);
    }
}

void downheap (int nod)
{
    int son;
    do
    {
        son = 0;
        if (2*nod<=l)
        {
            son=2*nod;
            if (2*nod+1<=l && a[h[2*nod+1]]<a[h[2*nod]])
                son=2*nod+1;
            if (a[h[son]]>=a[h[nod]])
                son = 0;
        }
        if (son)
        {
            swap (poz[h[nod]],poz[h[son]]);
            swap (h[nod],h[son]);
            nod=son;
        }
    }
    while (son);
}

int main ()
{
    freopen ("heapuri.in","r",stdin);
    freopen ("heapuri.out","w",stdout);
    int i,x,cod;
    scanf ("%d",&m);
    for (i=1; i<=m; ++i)
    {
        scanf ("%d",&cod);
        if (cod==1)
        {
            scanf ("%d",&x);
            a[++n]=x;
            poz[h[++l]=n]=l;
            upheap (n);
        }
        else if (cod==2)
        {
            scanf ("%d",&x);
            poz[h[l]]=poz[x];
            swap (h[poz[x]],h[l]);
            --l;
            if (poz[x]>1 && a[h[poz[x]]]<a[h[poz[x]/2]])
                upheap (poz[x]);
            else
                downheap (poz[x]);
            poz[x]=0;
        }
        else
            printf ("%d\n",a[h[1]]);
    }
    return 0;
}