#include <fstream>

using namespace std;

const int NMAX= 200000;

int n, k, nr, nr1, x, tip;

int h[NMAX+1], pos[NMAX+1], a[NMAX+1];

ifstream in( "heapuri.in" );
ofstream out( "heapuri.out" );

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 ()
{
    in >> x;
    a[++nr1]= x;
    pos[nr1]= nr;
    h[++nr]= nr1;
    up(nr);
}

void fa2 ()
{
    int y;
    in >> x;
    y=pos[x];
    swap ( pos[x], nr );
    nr--;
    dw (y,nr);



}

void fa3 ()
{
    out << a[h[1]] << '\n';
}

int main()
{
    in >> n;
    for( int i= 1; i<=n; ++i )
    {
        in >> tip;
        if (tip==1) fa1 ();
        else if (tip==2) fa2 ();
        else fa3 ();
    }
    return 0;
}