#include <fstream>
#include <iostream>
#include <vector>
#include <cstdio>

using namespace std;


struct nod
{
	int key;
	int chrOrder;
};

nod *heap;
int nr_elem_in_heap, chron_order;
int *position_vec;


int main()
{
	FILE *in = fopen("heapuri.in", "r");
	FILE *out = fopen("heapuri.out", "w");

	int n; fscanf(in, "%d", &n);//in >> n;


	heap = new nod[200001];
	position_vec = new int[200001];
	nr_elem_in_heap = 1;
	chron_order = 1;
	nod no; no.key = -1; no.chrOrder = -1;
	//heap.push_back(n);
	heap[0] = no;

	position_vec[0] = -1;

	for (int i = 0; i < n; i++)
	{
		int choice; fscanf(in, "%d", &choice); //in >> choice;
		if (choice == 1)
		{
			int x; fscanf(in, "%d", &x);//in >> x;
			nod nodul;
			nodul.key = x;
			nodul.chrOrder = chron_order;
			nr_elem_in_heap++;



			heap[nr_elem_in_heap - 1] = (nodul);
			//position_vec.push_back(nr_elem_in_heap - 1);

			position_vec[chron_order] = nr_elem_in_heap - 1;
			chron_order++;

			int pos = nr_elem_in_heap - 1;

			while (pos > 1 && heap[pos].key < heap[pos / 2].key)
			{

				nod a = heap[pos], b = heap[pos / 2], temp;

				position_vec[b.chrOrder] = position_vec[a.chrOrder];
				position_vec[a.chrOrder] /= 2;

				temp = heap[pos];
				heap[pos] = heap[pos / 2];
				heap[pos / 2] = temp;

				pos /= 2;
			}


		}

		else if (choice == 2)
		{
			int x; fscanf(in, "%d", &x); //in >> x;

			int pos = position_vec[x];

			heap[pos] = heap[nr_elem_in_heap - 1];//heap.back();
			nr_elem_in_heap--;

			position_vec[heap[pos].chrOrder] = pos;

			while (pos > 1 && heap[pos].key < heap[pos / 2].key)
			{

				nod a = heap[pos], b = heap[pos / 2], temp;

				position_vec[b.chrOrder] = position_vec[a.chrOrder];
				position_vec[a.chrOrder] /= 2;

				temp = heap[pos];
				heap[pos] = heap[pos / 2];
				heap[pos / 2] = temp;

				pos /= 2;
			}

			while (pos * 2 < nr_elem_in_heap)
			{
				int val_left, val_right;
				val_left = heap[pos * 2].key;
				if (nr_elem_in_heap > pos * 2 + 1)
					val_right = heap[pos * 2 + 1].key;
				else
					val_right = 1000000001;

				if (heap[pos].key <= val_right && heap[pos].key <= val_left)
					break;

				if (val_right < val_left)
				{
					nod temp = heap[pos];
					heap[pos] = heap[pos * 2 + 1];
					heap[pos * 2 + 1] = temp;

					position_vec[heap[pos].chrOrder] = pos;
					position_vec[heap[pos * 2 + 1].chrOrder] = pos * 2 + 1;

					pos = pos * 2 + 1;
				}
				else
				{
					nod temp = heap[pos];
					heap[pos] = heap[pos * 2];
					heap[pos * 2] = temp;

					position_vec[heap[pos].chrOrder] = pos;
					position_vec[heap[pos * 2].chrOrder] = pos * 2;

					pos = pos * 2;
				}
			}
		}

		else if (choice == 3)
		{
			fprintf(out, "%d\n", heap[1].key);
			//out << heap[1].key << endl;
		}
	}


	delete[] heap;
	delete[] position_vec;

	return 0;
}