#include <iostream>
#include<fstream>
#include<assert.h>
using namespace std;

ifstream f("heapuri.in");
ofstream g("heapuri.out");

int n, l, nr, a[200010], heap[200010], poz[200010];

void push(int x) {
	int aux;
	while (x / 2 && a[heap[x]] < a[heap[x / 2]]) {
		aux = heap[x];
		heap[x] = heap[x / 2];
		heap[x / 2] = aux;

		poz[heap[x]] = x;
		poz[heap[x / 2]] = x / 2;
		x = x / 2;
	}
}


void pop(int x) {
	int aux, k;
	k = 0;
	while (x != k) {
		k = x;

		if (k * 2 <= l && a[heap[x]] > a[heap[k * 2]])
			x = k * 2;

		if (k * 2 + 1 <= l && a[heap[x]] > a[heap[k * 2 + 1]])
			x = k * 2 + 1;

		aux = heap[x];
		heap[x] = heap[k];
		heap[k] = aux;

		poz[heap[x]] = x;
		poz[heap[k]] = k;
	}
}

int main()
{
	int i, x, k;
    f >> n;

	for (i = 0; i < n; i++) {
		f >> k;

		if (k < 3) {
			f >> x;
		}

		if (k == 1) {
			l++;
			nr++;
			a[nr] = x;
			heap[l] = nr;
			poz[nr] = l;
			push(l);
		}
		else
            if (k == 2) {

			a[x] = -1;
			push(poz[x]);
			poz[heap[1]] = 0;
			heap[1] = heap[l--];
			poz[heap[1]] = 1;
			if (l > 1)
				pop(1);
		}
		else if(k == 3){
            g<<a[heap[1]]<<"\n";
		}
	}
	return 0;
}