#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, keys;

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(keys[k], keys[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(keys[son], keys[k]);
			k = son;
		}
	} while (son);
}
void build_heap(Heap H, int &n, int k){
	if (n == 1) return;
	if (father(k) > 0 && H[k] < H[father(k)])  percolate(H, n, k);
	else sift(H, n, k);
}

int main()
{
	int times, x, op, v[MAX_HEAP_SIZE], n = 0, last;
	fin >> times;
	pos.push_back(0);  keys.push_back(0);

	for (int i = 1; i <= times; i++){
		fin >> op;
		if (op == 1 || op == 2)  {
			fin >> x;
			if (op == 1){
				v[++n] = x;
				pos.push_back(n);
				keys.push_back(n);
				build_heap(v, n, n);
			}
			else {
				v[pos[x]] = v[n];
				pos[keys[n]] = pos[x];
				keys[pos[x]] = keys[n--];
				build_heap(v, n, pos[x]);
			}
		}
		else fout << v[1] << "\n";

	}

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