#include <fstream>
#include <iostream>
using namespace std;

const int dim = 200003;

ifstream fin("heapuri.in");
ofstream fout("heapuri.out");

int v[dim], h[dim], p[dim];
int vi, hi, pi;

void mySwap(int p1, int p2) {
    int aux = h[p1];
    h[p1] = h[p2];
    h[p2] = aux;

    p[h[p1]] = p1;
    p[h[p2]] = p2;
}

void goUp(int poz) {
    while( v[h[poz]] < v[h[poz / 2]] ) {
        mySwap(poz, poz / 2);
        poz /= 2;
    }
}

void goDown(int poz) {
    int son;

    do {

        son = 0;

        if( poz * 2 <= hi )
            son = poz * 2;

        if( poz * 2 + 1 <= hi && v[h[poz * 2 + 1]] < v[h[son]] )
            son = poz * 2 + 1;

        if( son ) {
            mySwap(son, poz);
            poz = son;
        }

    } while( son );
}

int main() {
    int n, op, nr;
    fin >> n;

    for(int i = 0; i < n; i++) {
        fin >> op;
        if( op < 3 ) fin >> nr;

        if( op == 1 ) {
            v[++vi] = nr;
            p[vi] = vi;
            h[++hi] = vi;

            goUp(hi);
        } else if( op == 2 ) {
            mySwap(p[nr], hi--);

            if( h[p[nr]] > 1 && v[h[p[nr]]] <  v[h[p[nr] / 2]] )
                goUp(p[nr]);
            else 
                goDown(p[nr]);

        } else {
            cout << v[ h[1] ] << '\n';
        }
    }

    return 0;
}