#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;
typedef int Heap[MAX_HEAP_SIZE];
#define father(x) x / 2
#define left_son(x) x * 2
#define right_son(x) x * 2 + 1
vector <int> pos;
int order[MAX_HEAP_SIZE], v[MAX_HEAP_SIZE];

void percolate(Heap H, int n, int k){
	int key = H[k];
	while (k > 1 && H[father(k)] > key){
		H[k] = H[father(k)];
		swap(pos[pos[father(k)]], pos[pos[k]]);
		swap(order[k], order[father(k)]);
		k = father(k);
	}
	H[k] = key;
}
void sift(Heap H, int n, int k){
	int son;
	do{
		son = left_son(k);
		if (right_son(k) <= n && right_son(k) < son)  son = right_son(k);
		if (H[k] <= H[son] || son > n)  son = 0;
		if (son){
			swap(H[k], H[son]);
			swap(pos[k], pos[son]);
			swap(order[k], order[son]);
			k = son;
		}
	} while (son);
}
void build_heap(Heap H, int n, int k){
	if (father(k) > 0 && H[k] < H[father(k)])  percolate(H, n, k);
	else sift(H, n, k);
}

int main()
{
	int times, x, op, n = 0, total = 0;
	fin >> times;
	pos.push_back(0);

	for (int i = 1; i <= times; i++){
		fin >> op;

		if (op == 1)
		{
			fin >> x;  v[++n] = x;  order[n] = ++total;
			pos.push_back(n);
			build_heap(v, n, n);
		}
		else if (op == 2)
		{
			fin >> x;
			if (pos[x] > n / 2) { v[pos[x]] = 0; continue; }
			v[pos[x]] = v[n]; v[n] = 0;
			pos[order[n]] = pos[x];
			order[pos[x]] = order[n]; order[n] = 0;
			build_heap(v, --n, pos[x]);
		}
		else fout << v[1] << "\n";

	}

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