#include <fstream>
#include <algorithm>
#define DMAX 200001

using namespace std;

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

int n, i, op, x;
int poz[DMAX];
struct elem {int inf; int poz;} H[DMAX];

void inserare (int);
void urc_elem (int);
void cobor_elem (int);

int main()
{
    fin >> n;
    for (i = 1; i <= n; i++)
    {
        fin >> op;
        if (op == 1)
        {
            fin >> x; poz[0]++;
            inserare (x);
        }
        else if (op == 2)
            {
                fin >> x;
                H[poz[x]].inf = -1000000000;
                urc_elem (poz[x]);

                H[1] = H[H[0].inf]; poz[H[1].poz] = 1; H[0].inf--;
                cobor_elem (1);
            }
            else fout << H[1].inf << '\n';
    }
    return 0;
}

void inserare (int inf)
{
    int fiu, tata;
    fiu = ++H[0].inf;
    tata = fiu/2;

    while (tata && H[tata].inf > inf)
    {
        H[fiu] = H[tata]; poz[H[fiu].poz] = fiu;
        fiu = tata;
        tata /= 2;
    }

    H[fiu].inf = inf;
    H[fiu].poz = poz[0];
    poz[poz[0]] = fiu;
}

void urc_elem (int i)
{
    int fiu = i, tata = i/2;
    while (tata)
    {
        swap (H[fiu], H[tata]);
        swap (poz[H[fiu].poz], poz[H[tata].poz]);
        fiu = tata; tata = fiu/2;
    }
}

void cobor_elem (int i)
{
    int inf = H[i].inf, tata = i, fiu = 2*i;
    while (fiu <= H[0].inf)
    {
        if (fiu+1 <= H[0].inf && H[fiu].inf > H[fiu+1].inf) fiu++;
        // fiu indica cel mai mic dintre fii
        if (H[fiu].inf < inf)
        {
            swap (H[tata], H[fiu]);
            swap (poz[H[tata].poz], poz[H[fiu].poz]);
            tata = fiu;
            fiu = 2*tata;
        }
        else break;
    }
}