#include <fstream>
#define maxsize 200010

using namespace std;

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

typedef int Heap[maxsize];

Heap H;            //heap cu valorile din A[H[]];
                   //A[H[K]] - valoarea elementului de pe pozitia H[K] din A;
                   //H[K] - pozitia valorii a K-a din A
int NR, L, N;      //NR - numar de valori; L - numarul actual de valori din heap; N - numarul de cerinte
int A[maxsize];    //vector cu valorile in ordinea in care intra
int ORDER[maxsize];//ORDER[K] - pozitia elementului introdus al K-lea in heap - curenta
                   //ORDER[K] = 0; - atunci cand elementul introdus al K-lea e sters

void sift (int pos)
{
    //se introduce pozitia elementului care se doreste a fi cernut
    int son;

    while (pos != son)
    {
        son = pos;

        //se cauta fiu mai mic

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

        swap (H[pos], H[son]);

        ORDER[H[pos]] = pos;
        ORDER[H[son]] = son;

    }
}

void percolate (int pos)
{
    int key = A[H[pos]];

    while (pos > 1 && key < A[H[pos / 2]])
    {
        swap (H[pos], H[pos / 2]);

        ORDER[H[pos]] = pos;
        ORDER[H[pos / 2]] = pos / 2;

        pos = pos / 2;
    }
}

int main()
{

    int i;
    int x;
    int y;

    fin >> N;

    for (i = 1; i <= N; ++i)
    {
        fin >> x;

        if (x == 1)
        {
            fin >> y;

            ++NR;
            ++L;
            A[NR] = y;
            H[L] = NR;
            ORDER[NR] = L;

            percolate(L);
        }
        else if (x == 2)
        {
            fin >> y;

            A[y] = -1;
            percolate(ORDER[y]);

            ORDER[H[1]] = 0;    //elementul de pe A[H[1]] = -1, deci va fi cel mai mic, conform a ceea ce este mai sus
                                //deci il vom sterge din ORDER
            H[1] = H[L--];
            ORDER[H[1]] = 1;
            if (L>1)
                sift(1);

        }

        else
           fout << A[H[1]] << "\n";
    }

    return 0;

}