#include <iostream>
#include <fstream>

using namespace std;

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

int v[200001], ins[200001], nr_elem_heap, poz[200001], nr_inserate;

void inter(int &a, int &b){
    int aux;
    aux = a;
    a = b;
    b = aux;
}
void operatia_1(int x){

    nr_elem_heap++;
    v[nr_elem_heap] = x;
    poz[++nr_inserate]= x;
    int nr_elem_heap2 = nr_elem_heap;

    while(v[nr_elem_heap2 / 2] > v[nr_elem_heap2] && nr_elem_heap2 >= 2){
        inter(v[nr_elem_heap2 / 2], v[nr_elem_heap2]);
        inter(poz[nr_elem_heap2 / 2], poz[nr_elem_heap2]);
        nr_elem_heap2 /= 2;
    }
}

void operatia_2(int x){

    v[poz[ins[x]]] = v[nr_elem_heap];
    --nr_elem_heap;

    int nr_elem_heap2 = nr_elem_heap;

    while(v[nr_elem_heap2 / 2] > v[nr_elem_heap2] && nr_elem_heap2 >= 1){
        inter(v[nr_elem_heap2 / 2], v[nr_elem_heap2]);
        inter(poz[nr_elem_heap2 / 2], poz[nr_elem_heap2]);
        nr_elem_heap2 /= 2;
    }

    while(((v[nr_elem_heap2] > v[2 * nr_elem_heap2 + 1] || v[nr_elem_heap2] > v[2 * nr_elem_heap2])) && nr_elem_heap2 < nr_elem_heap){
        if(v[2 * nr_elem_heap2 + 1] > v[2 * nr_elem_heap2]){
            inter(v[nr_elem_heap2 * 2], v[nr_elem_heap2]);
            inter(poz[nr_elem_heap2 * 2], poz[nr_elem_heap2]);
            nr_elem_heap2 *= 2;
        } else {
            inter(v[nr_elem_heap2 * 2 + 1], v[nr_elem_heap2]);
            inter(poz[nr_elem_heap2 * 2 + 1], poz[nr_elem_heap2]);
            nr_elem_heap2 = nr_elem_heap2 * 2 + 1;
        }
    }
}

void operatia_3(){
    fout<<v[1]<<'\n';
}

int main()
{
    int nr_operatii, i, operatie, x;
    fin>>nr_operatii;
    for(i = 1; i <= nr_operatii; ++i){
        fin>>operatie;
        if(operatie < 3){
            fin>>x;
        }
        switch(operatie){
            case 1: operatia_1(x); break;
            case 2: operatia_2(x); break;
            case 3: operatia_3(); break;
        }
    }
    return 0;
}