#include <fstream>
using namespace std;

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

#define MAXN 200010

int index_heap,aux, L_Val[MAXN], Heap[MAXN], Poz[MAXN]; // Heap este practic ordinea elementelor daca le am construi ca un arbore. 
																	 // A este lista elementelor ce sunt in heap, ea nu se schimba
void push(int x)
{
	

	while (x / 2 && L_Val[Heap[x]] < L_Val[Heap[x / 2]])
	{
		// rearanjam practic intr-un min heap, mai intai facem switch 2 cu 9. etc.
		aux = Heap[x];
		Heap[x] = Heap[x / 2];
		Heap[x / 2] = aux;

		Poz[Heap[x]] = x;
		Poz[Heap[x / 2]] = x / 2;
		x /= 2;
	}
}

void pop(int x)
{
	int  y = 0;

	while (x != y)
	{
		y = x;

		if (y * 2 <= index_heap && L_Val[Heap[x]] > L_Val[Heap[y * 2]]) x = y * 2;
		if (y * 2 + 1 <= index_heap && L_Val[Heap[x]] > L_Val[Heap[y * 2 + 1]]) x = y * 2 + 1;

		aux = Heap[x];
		Heap[x] = Heap[y];
		Heap[y] = aux;

		Poz[Heap[x]] = x;
		Poz[Heap[y]] = y;
	}
}

int main()
{
	int N, x, index_vector = 0, key;
	fin >> N;
	for (int i = 0; i < N; i++)
	{
		fin >> key;

		if (key == 1)
		{
			fin >> x;
			L_Val[++index_vector] = x; // Adaugam numarul in lista de valori
			Heap[++index_heap] = index_vector; // adaugam noul indice
			Poz[index_vector] = index_heap; // adaugam noul indice

			push(index_heap);
		}

		else if (key == 2)
		{
			fin >> x;
			L_Val[x] = -1;
			push(Poz[x]);

			Poz[Heap[1]] = 0;
			Heap[1] = Heap[index_heap--];
			Poz[Heap[1]] = 1;
			pop(1);
		}

		else if (key == 3) fout << L_Val[Heap[1]] << "\n";
	}
	return 0;
}