#include <fstream>
#include <algorithm>

using namespace std;

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

int N, M;
int nr;
int H[200002], posH[200002], posAdd[200002];

int father(int nod)
{
    return nod / 2;
}

int left_son(int nod)
{
    return 2 * nod;
}

int right_son(int nod)
{
    return 2 * nod + 1;
}

void percolate(int nod) // urca
{
    while ((nod > 1) && H[nod] < H[father(nod)])
    {
        swap(H[nod], H[father(nod)]);
        swap(posH[posAdd[nod]], posH[posAdd[father(nod)]]);
        swap(posAdd[nod], posAdd[father(nod)]);
        nod = father(nod);
    }
}

void sift(int nod) // coboara
{
    int son = 1;
    while (son)
    {
        //son = 0;
        //if (left_son(nod) <= N && H[nod] > H[left_son(nod)] && H[left_son(nod)] > H[right_son(nod)]) son = left_son(son);
        //else if (right_son(nod) <= N && H[nod] > H[right_son(nod)] && H[right_son(nod)] > H[left_son(son)]) son = right_son(son);
        //else son = 0;
            son = 0;
        if (left_son(nod) <= N)
        {
            son = left_son(nod);
            if (right_son(nod) <= N && H[right_son(nod)] < H[left_son(nod)])
                son = right_son(nod);
            if (H[son] >= H[nod])
                son = 0;
        }

        if (son)
        {
            swap(H[nod], H[son]);
            swap(posH[posAdd[nod]], posH[posAdd[son]]);
            swap(posAdd[nod], posAdd[son]);

            nod = son;
        }
    }
}

void cut(int nod)
{
    swap(H[nod], H[N]);
    swap(posH[posAdd[nod]], posH[posAdd[N]]);
    swap(posAdd[nod], posAdd[N]);
    --N;

    if ((nod > 1) && H[nod] < H[father(nod)]) percolate(nod);
    else sift(nod);
}

int main()
{
    fin >> M;
    for (int i = 1, cod; i <= M; ++i)
    {
        fin >> cod;
        int numar;
        if (cod == 1)
        {
            fin >> numar;

            ++N;
            ++nr;
            H[N] = numar;
            posAdd[N] = nr;
            posH[nr] = N;

            percolate(N);

        }
        else if (cod == 2)
        {
            fin >> numar;

/*
            for (int i = 1; i <= N; ++i)
                fout << H[i] << ' ';
            fout << '\n';
            for (int i = 1; i <= N; ++i)
                fout << posAdd[i] << ' ';
            fout << '\n';
            for (int i = 1; i <= nr; ++i)
                fout << posH[i] << ' ';
            fout << '\n';
            */


            cut(posH[numar]);
/*
            for (int i = 1; i <= N; ++i)
                fout << H[i] << ' ';
            fout << '\n';
            for (int i = 1; i <= N; ++i)
                fout << posAdd[i] << ' ';
            fout << '\n';
            for (int i = 1; i <= nr; ++i)
                fout << posH[i] << ' ';
            fout << '\n';
            fout << '\n';
            fout << '\n';
*/
        }
        else fout << H[1] << '\n';
    }

/*
    for (int i = 1; i <= N; ++i)
        fout << H[i] << ' ';
    fout << '\n';
    for (int i = 1; i <= N; ++i)
        fout << posAdd[i] << ' ';
    fout << '\n';
    for (int i = 1; i <= nr; ++i)
        fout << posH[i] << ' ';
    fout << '\n';
    */


    fin.close();
    fout.close();
    return 0;
}