#include <cstdio>
using namespace std;
int k,a[200010],b[200010];
void urc(int x)
{
int aux,q=x >> 1;

    while (q!=0 && a[x]<a[q])
    {
        aux = a[x];
        a[x] = a[q];
        a[q] = aux;
        aux = b[x];
        b[x] = b[q];
        b[q] = aux;
        x >>= 1;
        q >>= 1;
    }
}
void cobor(int x)
{
    int aux, y = 0,w;

    while (x != y)
    {
         y = x;
         w = y << 1;
        if (w<=k && a[x]>a[w]) x = w;
        ++w;
        if (w<=k && a[x]>a[w]) x = w;

        aux = a[x];
        a[x] = a[y];
        a[y] = aux;
        aux = b[x];
        b[x] = b[y];
        b[y] = aux;

    }
}
int main()
{
    int j,n,nr=0,w,i,q;
    short e;
    freopen("heapuri.in","r",stdin);
    freopen("heapuri.out","w",stdout);
    scanf("%d",&n);
    for(j=0;j<n;++j)
    {
        scanf("%hd",&e);
        if(e==1)
        {
            ++k;
            scanf("%d",&a[k]);
            ++nr;
            b[k]=nr;
            urc(k);
        }
        else if(e==2)
        {
            scanf("%d",&w);
            i=1;
            while(e!=0)
                if (b[i]==w) e=0;
                else ++i;
            a[i]=a[k];
            b[i]=b[k];
            --k;
            if(i!=1)
            {
                q=i >> 1;
                if(a[i]<a[q])
                {
                    w=a[i];
                    a[i]=a[q];
                    a[q]=w;
                    w=b[i];
                    b[i]=b[q];
                    b[q]=w;
                    urc(q);
                }
                else
                {
          cobor(i);

                }
            }
            else
            {
cobor(i);
            }

        }
        else
        printf("%d\n",a[1]);
    }
    return 0;
}