#include <iostream>
#include <fstream>

using namespace std;

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

int ins[200001], nr_elem_heap, poz[200001], nr_inserate;
struct heap{
    int val, poz;// pozitia pe care a fost inserat initial
}v[200001];
void inter(heap &a, heap &b){
    heap aux = a;
    a = b;
    b = aux;
}
void inter2(int &a, int &b){
    int aux;
    aux = a;
    a = b;
    b = aux;
}
void operatia_1(int x){

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

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

}
void up (int p)
{
    if(p > 1 && v[p].val < v[p/2].val)
    {
        swap(v[p], v[p/2]);
        swap(poz[v[p].poz], poz[v[p/2].poz]);
        up(p/2);
    }

}

void down(int p)
{
    if(2*p <= nr_elem_heap)
    {
        int x = p;
        if(v[2*p].val < v[x].val)
            x = 2*p;
        if(2*p + 1 <= nr_elem_heap && v[2*p + 1].val < v[x].val)
            x = 2*p + 1;
        if(x != p)
        {
            swap(v[p], v[x]);
            swap(poz[v[p].poz], poz[v[x].poz]);
            down(x);
        }

    }

}

void operatia_2(int x){

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

    int nr_elem_heap2 = nr_elem_heap;

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

    while((2 * nr_elem_heap2 + 1 <= nr_elem_heap && v[nr_elem_heap2].val > v[2 * nr_elem_heap2 + 1].val) ||
           (2 * nr_elem_heap2 <= nr_elem_heap && v[nr_elem_heap2].val > v[2 * nr_elem_heap2].val)){
        if(v[2 * nr_elem_heap2 + 1].val > v[2 * nr_elem_heap2].val){
            inter(v[nr_elem_heap2 * 2], v[nr_elem_heap2]);
            inter2(poz[v[nr_elem_heap2 * 2].poz], poz[v[nr_elem_heap2].poz]);
            nr_elem_heap2 *= 2;
        } else {
            inter(v[nr_elem_heap2 * 2 + 1], v[nr_elem_heap2]);
            inter2(poz[v[nr_elem_heap2 * 2 + 1].poz], poz[v[nr_elem_heap2].poz]);
            nr_elem_heap2 = nr_elem_heap2 * 2 + 1;
        }
    }
    */
    up(poz[x]);
    down(poz[x]);
}

void operatia_3(){
    fout<<v[1].val<<'\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;
}