#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 k) {
    int son;
    do
    {
        son = 0;
        // Cautam un fiu mai mic ca tatal
        if (2 * k <= l) {
            son = 2 * k;
            if (2 * k + 1 <= l && a[heap[2 * k + 1]] < a[heap[son]])
                son = 2 * k + 1;
            if (a[heap[k]] < a[heap[son]])
                son = 0;
        }

        // Daca am gasit un fiu mai mic ca tatal dam swap si continuam procedeul
        if (son) {
            swap(heap[k], heap[son]);
            pos[heap[son]] = k;
            pos[heap[k]] = son;
            k = son;
        }

    } while (son);
}

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);
}

void up_heap (int key) {
    heap[++n] = key;
    percolate(n);
}

void down_heap () {
    heap[1] = heap[n--];
    sift(1);
}

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;
}