#include <fstream>
#include <iostream>
#include <vector>
using namespace std;
ifstream fin("heapuri.in");
ofstream fout("heapuri.out");
vector<int> heap, pos, val;
void insertInHeap(int poz) {
    while (poz / 2 > 0 && val[poz] < val[poz / 2]) {
        swap(heap[poz], heap[poz / 2]);
        pos[heap[poz]] = poz;
        pos[heap[poz / 2]] = poz;
        poz /= 2;
    }
}
void pop() {
    int poz = 1, pozInitial = 0;
    while (poz != pozInitial) {
        pozInitial = poz;
        if (pozInitial * 2 < heap.size() && val[heap[poz]] > val[heap[pozInitial * 2]]) {
            poz = pozInitial * 2;
        }
        if (pozInitial * 2 + 1 < heap.size() && val[heap[poz]] > val[heap[pozInitial * 2 + 1]]) {
            poz = pozInitial * 2 + 1;
        }
        swap(heap[poz], heap[pozInitial]);
        pos[heap[poz]] = poz;
        pos[heap[pozInitial]] = pozInitial;
    }
}
int main()
{
    int N;
    int c, x;
    fin >> N;
    heap.push_back(-1); val.push_back(-1); pos.push_back(-1);
    for (int i = 0; i < N; ++i) {
        fin >> c;
        if (c == 1) {
            fin >> x;
            val.push_back(x);
            heap.push_back(val.size() - 1);
            pos[val.size() - 1] = heap.size() - 1;
            insertInHeap(heap.size() - 1);
        }
        if (c == 2) {
            fin >> x;
            val[x] = -1;
            insertInHeap(pos[x]);
            pos[heap[1]] = 0;
            heap[1] = heap[heap.size() - 1];
            pos[heap[1]] = 1;
            heap.pop_back();
            if (heap.size() > 2) {
                pop();
            }
        }
        if(c == 3) {
            fout << val[heap[1]] << "\n";
        }
    }
    return 0;
}