#include <stdio.h>

int a,b,c,d,h[400001],p[400001],p2[400001],n,m;

void percolate(int x)
{
    while ((x>1)&&(h[x]<h[x/2]))
    {
        a=p2[x];b=p[a];c=p2[x/2];d=p[c];
        p[a]=d;p[c]=b;p2[x]=c;p2[x/2]=a;
        a=h[x];h[x]=h[x/2];h[x/2]=a;
        x/=2;
    }
}

void sift (int x)
{

    while (((2*x<=n)&&(h[x]>h[2*x]))||((2*x<n)&&(h[x]>h[2*x+1])))
    {
        if ((2*x<n)&&(h[2*x+1]<h[2*x]))
        {
            a=p2[x];b=p[a];c=p2[2*x+1];d=p[c];
            p[a]=d;p[c]=b;p2[x]=c;p2[2*x+1]=a;
            a=h[x];h[x]=h[2*x+1];h[2*x+1]=a;
            x+=x+1;
        }
        else
        {
            a=p2[x];b=p[a];c=p2[2*x];d=p[c];
            p[a]=d;p[c]=b;p2[x]=c;p2[2*x]=a;
            a=h[x];h[x]=h[2*x];h[2*x]=a;
            x*=2;
        }
    }
}

int main()
{
    int i,x;
    freopen("heapuri.in","r",stdin);
    freopen("heapuri.out","w",stdout);
    scanf("%d",&m);
    for (i=1;i<=m;++i)
    {
        scanf("%d",&x);
        if (x==1)
        {
            scanf("%d",&x);
            ++n;h[n]=x;++a;p[a]=n;p2[n]=a;
            percolate(n);
        }
        else if (x==2)
        {
            scanf("%d",&x);
            x=p[x];
            a=p2[x];b=p[a];c=p2[n];d=p[c];
            p[a]=d;p[c]=b;p2[x]=c;p2[n]=a;
            a=h[x];h[x]=h[n];h[n]=a;--n;
            sift(x);
        }
        else printf("%d\n",h[1]);
    }
    return 0;
}