#include<iostream>
#include<fstream>

using namespace std;

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

const int MAXN = 200010;

int N, L, NR;

int A[MAXN], pos[MAXN], H[MAXN];

void push(int x)
{
	int aux;
	
	while((x >> 1) && (A[ H[x] ] < A[ H[x >> 1] ])){
		aux = H[x];
		H[x] = H[x >> 1];
		H[x >> 1] = aux;
		
		pos[ H[x] ] = x;
		pos[ H[x >> 1] ] = x >> 1;
		x >>= 1;
	}
}

void pop(int x)
{
	int aux, y = 0;
	
	while(x != y){
		y = x;
		
		if(((y << 1) <= L) && (A[ H[x] ] > A[ H[y << 1] ])) x = (y << 1);
		if(((y << 1) + 1 <= L) && (A[ H[x] ] > A[ H[(y << 1) + 1] ])) x = (y << 1) + 1;
		
		aux = H[x];
		H[x] = H[y];
		H[y] = aux;
		
		pos[ H[x] ] = x;
		pos[ H[y] ] = y;
	}
}

int main()
{
	int i, x, cod;
	
	in >> N;
	
	for(i = 1; i <= N; ++i){
		in >> cod;
		
		if(cod < 3)
			in >> x;
		
		if(cod == 1){
			L++, NR++;
			A[NR] = x;
			H[L] = NR;
			pos[NR] = L;
			
			push(L);
		}
		
		if(cod == 2){
			A[x] = -1;
			push(pos[x]);
			
			pos[ H[1] ] = 0;
			H[1] = H[ L-- ];
			pos[ H[1] ] = 1;
			
			if(L > 1)
				pop(1);
		}
		
		if(cod == 3)
			out << A[ H[1] ] << "\n";
	}
	
	return 0;
}