#include <stdio.h>


using namespace std;
int i,n,k,h[200004],pos[200004],a[200004],nr,nr1,x,tip;
FILE *f,*g;
void swap (int i,int j)
{
    int aux;
    aux=h[j];
    h[j]=h[i];
    h[i]=aux;
    pos[h[i]]=i;
    pos[h[j]]=j;
}
void dw (int k,int n)
{
    int st=k*2;
    if (st<=n)
    {
        if (st+1<=n) if (a[h[st+1]]<a[h[st]]) st++;
        if (a[h[st]]<a[h[k]])
        {
            swap (st,k);
            dw(st,n);
        }
    }
}
void up (int k)
{
    int tata=k/2;
    if (tata>=1)
    {
        if (a[h[tata]]>a[h[k]])
        {
            swap (tata,k);
            up(tata);
        }
    }
}
void fa1 ()
{
    fscanf (f,"%d",&x);
    a[++nr1]=x;
    pos[nr1]=nr;
    h[++nr]=nr1;
    up (nr);
}
void fa2 ()
{   int y;
    fscanf (f,"%d",&x);
    y=pos[x];
    swap (pos[x],nr);
    nr--;
    dw (y,nr);



}
void fa3 ()
{
    fprintf (g,"%d\n",a[h[1]]);
}
int main()
{f=fopen ("heapuri.in","r");
 g=fopen ("heapuri.out","w");
 fscanf (f,"%d",&n);
 for (i=1;i<=n;i++)
{
    fscanf (f,"%d",&tip);
    if (tip==1) fa1 ();
     else if (tip==2) fa2 ();
       else fa3 ();
}

    return 0;
}