#include <cstdio>
using namespace std;
int k,a[200010],b[200010];
void urc(int k1)
{
    int q=k1 >> 1,w;
    if(q!=0)
    if (a[k1]<a[q])
    {
        w=a[k1];
        a[k1]=a[q];
        a[q]=w;
        w=b[k1];
        b[k1]=b[q];
        b[q]=w;
        urc(q);
    }
}
void cobor(int k1)
{
    int q=k1 << 1,q1=q+1,w;
    if(q1<=k)
    {
        if (a[q]>=a[q1])
        {
            if (a[q1]<a[k1])
            {
                w=a[k1];
                a[k1]=a[q1];
                a[q1]=w;
                w=b[k1];
                b[k1]=b[q1];
                b[q1]=w;
                cobor(q1);
            }
        }
        else
        if (a[q]<a[k1])
            {
                w=a[k1];
                a[k1]=a[q];
                a[q]=w;
                w=b[k1];
                b[k1]=b[q];
                b[q]=w;
                cobor(q);
            }
        }
     else if(q==k)
         if (a[q]<a[k1])
            {
                w=a[k1];
                a[k1]=a[q];
                a[q]=w;
                w=b[k1];
                b[k1]=b[q];
                b[q]=w;
                cobor(q);
            }
}
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];
            --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;
}