# include <fstream>
# include <algorithm>
# include <vector>
using namespace std;
ifstream fin("heapuri.in");
ofstream fout("heapuri.out");

const int MAX_H = 200010;
int h[MAX_H], v[MAX_H], pos[MAX_H];
int x, t, p, u;

void shiftUp(int k) { // percolate
    while (k && v[h[k]] < v[h[k>>1]]) {
        swap(h[k], h[k>>1]);
        swap(pos[h[k]], pos[h[k>>1]]);
        k >>= 1;
    }
}

void shiftDown(int k) { // sift
    int i;
    while (i != k) {
        i = k;
        if ( (i<<1) <= h[0] && v[h[i<<1]] < v[h[k]] ) // caut in fiul drept
            k = i << 1;

        if ( (i<<1)+1 <= h[0] && v[h[(i<<1)+1]] < v[h[k]] ) // caut in fiul stang
            k = (i << 1) + 1;

        swap(pos[h[k]], pos[h[i]]);
        swap(h[k], h[i]);
    }
}

int main() {
    fin >> t;
    while (t--) {
        fin >> p;
        if (p == 1) {
            fin >> x;
            v[++v[0]] = x;
            h[++h[0]] = v[0];
            pos[v[0]] = h[0];

            shiftUp(h[0]);
        } else if (p == 2) {
            fin >> x;
            u = h[h[0]];
            swap(h[pos[x]], h[h[0]]);
            swap(pos[h[pos[x]]], pos[h[h[0]]]);

            --h[0];

            shiftUp(pos[u]);
            shiftDown(pos[u]);
        } else fout << v[h[1]] << "\n";
    }

    fin.close();
    fout.close();
    return 0;
}