#include<bits/stdc++.h>
using namespace std;
ifstream f("heapuri.in");
ofstream g("heapuri.out");
int v[200001], a[200001], pos[200001];
int n, tip, k, t, x;

void push(int x) {
	int aux;
	while(x/2 && a[v[x]] < a[v[x/2]])
	{
		swap(v[x], v[x/2]);
		pos[v[x]] = x;
		pos[v[x/2]] = x/2;
		x /= 2;
	}
}

void pop(int x)
{
	int aux, y = 0;
	while(x != y) {
		y = x;
		if(y * 2 <= k && a[v[x]] > a[v[y * 2]])
            x = y * 2;
		if(y * 2 + 1 <= k && a[v[x]] > a[v[y * 2 + 1]])
            x = y * 2 + 1;
		swap(v[x], v[y]);
		pos[v[x]] = x;
		pos[v[y]] = y;
	}
}

int main()
{
    f >> n;
    for(int i = 1; i <= n; i++) {
        f >> tip;
        if(tip == 1) {
            f >> x;
            k++;
            t++;
			a[t] = x;
			v[k] = t;
			pos[t] = k;
			push(k);
        }
        else if(tip == 2) {
            f >> x;
            a[x] = -1;
			push(pos[x]);
			pos[v[1]] = 0;
			v[1] = v[k];
			k--;
			pos[v[1]] = 1;
			if (k>1)
                pop(1);
        }
        else
            g << a[v[1]] << '\n';
    }
    return 0;
}