#include <iostream>
#include <fstream>
using namespace std;
ifstream f("heapuri.in");
ofstream g("heapuri.out");
int nod, v[200005], heap[200005], vector_pozitii[200005], lungime, k;
void push(int nod)
{
int var ;
while( nod / 2 != 0 && v [heap [nod]] < v [heap [nod / 2]])
{
    var = heap[nod];
    heap[nod] = heap[nod / 2];
    heap[nod / 2] = var;
    vector_pozitii[heap[nod ]] = nod;
    vector_pozitii[heap[nod / 2]] = nod / 2;
    nod = nod / 2;
}
}
void pop(int nod)
{
int var , t = 0;
while( nod != t)
{
    t = nod;
    if(t * 2 <= lungime && v[ heap[nod]] > v[ heap[ t*2]])
        nod = t * 2;
    if( t * 2 + 1 <= lungime && v[heap[nod]] > v[heap[t * 2 + 1]])
        nod = t * 2 + 1;
    var = heap[nod];
    heap[nod] = heap[t];
    heap[t] = var;
    vector_pozitii[heap[nod ]] = nod;
    vector_pozitii[heap[ t]] = t;
}
}
int main()
{
    int n, i, cod, x, y;

    f >> n;
    for( i = 1; i <= n; i++)
    {
        f >> cod;
        if( cod  == 1)
        {
            f >> x;
            lungime ++;
            k++;
            v[k] = x;
            heap[lungime] = k;
            vector_pozitii[k] = lungime;
            push(lungime);
        }
        else if( cod == 2)
        //intai incarc nodul respectiv pe cea mai mica pozitie si mai apoi il echilibrez
            //conform cerintei, voi scoate cel de-al x-lea element care a fost adaugat prin pop
        {
            f >> y;
            v[y] = -1;
            //if( vector_pozitii[y] != 0)
                push(vector_pozitii[y]);
            vector_pozitii[heap[1]] = 0; //am setat noua radacina
            heap[1] = heap[lungime];
            lungime--;
            vector_pozitii[heap[1]] = 1;
            if(lungime > 1)
                pop(1);

        }
            else if(cod == 3)
                g << v[heap[1]] << '\n';

    }
    return 0;

}