#include<fstream>
#define nmax 200006
using namespace std;
ifstream fin("heapuri.in");
ofstream fout("heapuri.out");

int H[nmax], N, ord[nmax], L;//indicii de aparitie si oridinea in care apar
int A[nmax];//retin val nodurilor

void insert(int x)
{


    while(x/2 && A[H[x/2]] > A[H[x]])
    {
        int aux = H[x/2];
        H[x/2] = H[x];
        H[x] = aux;
        ord[H[x]] = x;
        ord[H[x/2]] = x/2;
        x/=2;
    }

}

void sterge(int x)
{
    int aux , y = 0;
    while(y != x)
    {
        y = x;
        if(y * 2 <=L &&  A[H[x]] > A[H[x*2]] ) y = x*2;

        if(y * 2 + 1 <=L && A[H[x]] > A[H[x * 2 + 1]]) y= x * 2 + 1;

        aux = H[x];
        H[x] = H[y];
        H[y] = aux;
        ord[H[x]] = x;
        ord[H[y]] = y;
    }
}

void read()
{
    int cod, x, n;
    fin >>n ;
    for(int i = 1; i <= n; i++)
    {
        fin >> cod;
        if(cod < 3)
            fin >>x;
        if(cod == 1){
            ++L;++N;
            A[N] = x;
            ord[N] = L;
            H[L] = N;

            insert(L);//pozitionam nou nod care primeste initial ultimul indice in heap(L)
        }
        if(cod == 2)
        {

            A[x] = -1;
            insert(ord[x]);//mutam nodul care trebuie sters in nodul radacina
            ord[H[1]] = 0;
            H[1] = H[L];
            --L;

            ord[H[1]] = 1;

            if(L > 1)
                sterge(1);//stergem nodul radacina

            sterge(ord[x]);
        }
        if(cod == 3)
            fout << A[H[1]] <<'\n';
    }
}
int main()
{
    read();
    fin.close();
    return 0;

}