#include <iostream>
#include <fstream>

using namespace std;

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

void inter(int &a, int &b){
    int aux;
    aux = a;
    a = b;
    b = aux;
}
void operatia_1(int op, int x, int &nr_elem_heap, int v[], int ind[], int i){

    nr_elem_heap++;
    v[nr_elem_heap] = x;

    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(ind[nr_elem_heap2 / 2], ind[nr_elem_heap2]);
        nr_elem_heap2 /= 2;
    }
    ind[op] = nr_elem_heap2;
}

void operatia_2(int &nr_elem_heap, int v[], int poz, int ind[]){

    v[poz] = 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(ind[nr_elem_heap2 / 2], ind[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(ind[nr_elem_heap2 * 2], ind[nr_elem_heap2]);
            nr_elem_heap2 *= 2;
        } else {
            inter(v[nr_elem_heap2 * 2 + 1], v[nr_elem_heap2]);
            inter(ind[nr_elem_heap2 * 2 + 1], ind[nr_elem_heap2]);
            nr_elem_heap2 = nr_elem_heap2 * 2 + 1;
        }
    }
}

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

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