/* 
 * File:   main.cpp
 * Author: virtualdemon
 *
 * Created on January 25, 2010, 6:05 PM
 */
#include <fstream>
#define NMax 200001

/*
 *
 */
using namespace std;
int N=0, N2=0;
int Heap[NMax], Position[NMax], Element[NMax];
inline void swap( int& x, int& y )
{
    x+=y;
    y=x-y;
    x-=y;
}
void sift( int k )
{
    int son, right_son;
    while( true )
    {
        son=2*k;
        if( son > N )
            break;
        right_son=2*k+1;
        if( right_son <= N && Element[Heap[son]] > Element[Heap[right_son]] )
            son=right_son;
        if( Element[Heap[son]] >= Element[Heap[k]] )
            break;
        swap( Heap[k], Heap[son] );
        Position[Heap[k]]=k;
        Position[Heap[son]]=son;
        k=son;
    }
}
void percolate( int k )
{
    int key=Heap[k], f=k/2;
    while( k > 1 && Element[key] < Element[Heap[f]] )
    {
        swap( Heap[k], Heap[f] );
        Position[Heap[k]]=k;
        Position[Heap[f]]=f;
        k=f;
        f/=2;
    }
}
int main()
{
    int n, x, y, i;
    ifstream in("heapuri.in");
    ofstream out("heapuri.out");
    in>>n;
    for( i=0; i < n; ++i )
    {
        in>>x;
        if( x < 3 )
        {
            in>>y;
            if( 1 == x )
            {
                Element[++N2]=y;
                Position[N2]=N2;
                Heap[++N]=N2;
                percolate( N );
                continue;
            }
            if( 2 == x )
            {x=Position[y];
                Heap[x]=Heap[N];
                Position[Heap[N]]=x;
                --N;
                sift( x );
                continue;
            }
            continue;
        }
        out<<Element[Heap[1]]<<'\n';
    }
    return 0;
}