#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>
#include <stack>

using namespace std;

fstream fin("heapuri.in", ios::in);
fstream fout("heapuri.out", ios::out);

const int MAX_HEAP_SIZE = 200005;
#define father(x) x / 2
#define left_son(x) x * 2
#define right_son(x) x * 2 + 1
int heap_order[MAX_HEAP_SIZE], heap[MAX_HEAP_SIZE], pos[MAX_HEAP_SIZE];

void percolate(int k){
	int key = heap[k], order = heap_order[k];
	while (k > 1 && heap[father(k)] > key)
		heap[k] = heap[father(k)],
		heap_order[k] = heap_order[father(k)],
		pos[heap_order[k]] = k,
		k = father(k);

	heap[k] = key;
	heap_order[k] = order;
	pos[order] = k;
}
void sift(int k){
	while (true){
		int son = left_son(k);
		if (right_son(k) <= heap[0] && heap[right_son(k)] < heap[son])  son = right_son(k);
		if (heap[son] >= heap[k] || son > heap[0]) return;

		swap(heap[k], heap[son]);
		swap(heap_order[k], heap_order[son]);
		pos[heap_order[k]] = k;
		pos[heap_order[son]] = son;
	}
}


void build_heap(int k){
	if (k > heap[0]) return;
	if (heap[k] < heap[father(k)] && father(k) > 0)  percolate(k);
	else sift(k);
}

int main()
{
	int times, op, total = 0, x;
	fin >> times;

	for (int i = 1; i <= times; i++){
		fin >> op;
		if (op == 1){
			fin >> x;
			heap[++heap[0]] = x;
			heap_order[heap[0]] = ++total;
			pos[total] = heap[0];
			build_heap(heap[0]);
		}
		else if (op == 2){
			fin >> x;
			heap[pos[x]] = heap[heap[0]];             heap[heap[0]] = 0;
			pos[heap_order[heap[0]]] = pos[x];
			heap_order[pos[x]] = heap_order[heap[0]]; heap_order[heap[0]--] = 0;
			build_heap(pos[x]);
			pos[x] = 0;
		}
		else fout << heap[1] << "\n";
	}

	fin.close();
	fout.close();
	return 0;
}