#include <fstream>
using namespace std;
ifstream cin( "heapuri.in" );
ofstream cout( "heapuri.out" );

int n, v[ 200001 ], cod, x, p;
int nr, h[ 200001 ], pos[ 200001 ];

void push( int k )
{
	int aux;
	while( k > 1 && v[ h[ k ] ] < v[ h[ k / 2 ] ] )
	{
		aux = h[ k ];
		h[ k ] = h[ k / 2 ];
		h[ k / 2 ] = aux;
		pos[ h[ k ] ] = k;
		pos[ h[ k / 2 ] ] = k / 2;
		k /= 2;
	}
}

void pop( int k )
{
	int aux, t = 0;
	while ( k != t )
	{
		t = k;
		if ( t * 2 <= p && v[ h[ k ] ] > v[ h[ t * 2 ] ] ) k = t * 2;
		if ( t * 2 + 1 <= p && v[ h[ k ] ] > v[ h[ t * 2 + 1 ] ] ) k = t * 2 + 1;
		aux = h[ k ];
		h[ k ] = h[ t ];
		h[ t ] = aux;
		pos[ h[ k ] ] = k;
		pos[ h[ t ] ] = t;
	}
}

int main()
{
	int i;
	cin >> n;
	for ( i = 1; i <= n; i++ )
	{
		cin >> cod;
		if ( cod == 1 )
		{
			cin >> x;
			v[ ++nr ] = x;
			p++;
			h[ p ] = nr;
			pos[ nr ] = p;
			push( p );
		}
		else if ( cod == 2 )
		{
			cin >> x;
			v[ x ] = -1;
			push( pos[ x ] );
			pos[ h[ 1 ] ] = 0;
			h[ 1 ] = h[ p-- ];
			pos[ h[ 1 ] ] = 1;
			if ( p > 1 ) pop( 1 );
		}
		else cout << v[ h[ 1 ] ] << '\n';
	}
	return 0;
}