#include <iostream>
#include <cstdio>
#define nmax 200000
using namespace std;

int n,x,test,op,opx,k,k1;
int v[nmax],poz[nmax],ord[nmax];
///v[x] - al x-lea element din heap
///poz[x] - pozitia in heap a elementului inserat al x-lea
///ord[x] - al catelea a fost introdus elementul aflat pe poz x in heap
///x=v[poz[ord[x]]]

void urcare(int x)
{
    int tata=x/2;
    while(v[x] && v[x]<v[tata])
    {
        swap(v[x],v[tata]);
        swap(ord[x],ord[tata]);
        poz[ord[x]]=x;
        poz[ord[tata]]=tata;
        x/=2;
        tata/=2;
    }
}

void coborare(int x)
{
    int fiu,fius,fiud;
    fius=2*x; fiud=2*x+1;

    if (v[fius] && (v[fius]<v[fiud] || !v[fiud])) fiu=fius;
    else if (v[fiud]) fiu=fiud;
    else fiu=0;

    while(fiu && v[x]>v[fiu])
    {
        swap(v[x],v[fiu]);
        swap(ord[x],ord[fiu]);
        poz[ord[x]]=x;
        poz[ord[fiu]]=fiu;
        x=fiu;
        fius=2*x; fiud=2*x+1;

        if (v[fius] && (v[fius]<v[fiud] || !v[fiud])) fiu=fius;
        else if (v[fiud]) fiu=fiud;
        else fiu=0;
    }
}

int main()
{
    freopen("heapuri.in","r",stdin);
    freopen("heapuri.out","w",stdout);
    scanf("%d",&op);
    for(opx=1;opx<=op;opx++)
    {
        scanf("%d",&test);
        if (test==1)
        {
            scanf("%d",&v[++n]);
            ord[n]=++k;
            poz[ord[n]]=n;
            urcare(n);
        }
        else if (test==2)
        {
            scanf("%d",&k1);
            x=poz[k1];
            v[x]=v[n];
            v[n--]=0;

            if (v[x]<v[x/2]) urcare(x);
            else coborare(x);
        }
        else printf("%d\n",v[1]);
    }
    return 0;
}