#include <iostream>
#include <fstream>
#include <algorithm>

const int n_max = 200010;

using namespace std;

ifstream fin ("heapuri.in");
ofstream fout ("heapuri.out");
int heap[n_max], pos[n_max], a[n_max], n, l, nr;

void sift (int x) {
    int aux, y = 0;

    while (x != y)
    {
        y = x;

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

        aux = heap[x];
        heap[x] = heap[y];
        heap[y] = aux;

        pos[heap[x]] = x;
        pos[heap[y]] = y;
    }
}

void percolate (int k) {
    // Cat timp tatal este mai mare dam swap
    while (k > 1 && a[heap[k]] < a[heap[k / 2]]) {
        swap(heap[k], heap[k/2]);

        pos[heap[k]] = k;
        pos[heap[k/2]] = k/2;
        k = k / 2;
    }

}

void cut (int k) {
    heap[k] = heap[n];
    --n;

    if (k > 1 && heap[k] < heap[k/2])
        percolate(k);
    else
        sift(k);
}

int main()
{
    int cod, x;

    fin >> n;

    for (int i=1; i <= n; i++) {
        fin >> cod;
        if (cod == 1) {
            fin >> x;

            nr++; l++;
            a[nr] = x;
            heap[l] = nr;
            pos[nr] = l;

            percolate(l);
        }
        else if (cod == 3) {
            fout << a[heap[1]] << '\n';
        }
        else {
            fin >> x;
            a[x] = -1;
            percolate(pos[x]);

            pos[heap[1]] = 0;
            heap[1] = heap[l--];
            pos[heap[1]] = 1;
            if (l>1) sift(1);
        }
    }

    return 0;
}