#include <iostream>
#include <fstream>
#include <algorithm>

#define tat (x >> 1)
#define fiu1 (y << 1)
#define fiu2 (fiu1 + 1)

using namespace std;

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

const int Nmax = 200010;

int n, nr, lg, v[Nmax], h[Nmax], poz[Nmax];

void push(int x)
{
    while(tat && v[h[x]] < v[h[tat]])
    {
        swap(h[x], h[tat]);

        poz[h[x]] = x;
        poz[h[tat]] = tat;

        x = tat;
    }
}

void pop(int x)
{
    int y;
    while(x != y)
    {
        y = x;
        if(fiu1 <= lg && v[h[x]] > v[h[fiu1]]) x = fiu1;
        if(fiu2 <= lg && v[h[x]] > v[h[fiu2]]) x = fiu2;

        swap(h[x], h[y]);
        poz[h[x]] = x;
        poz[h[y]] = y;
    }
}

int main()
{
    fin>>n;
    for(int i=1; i<=n; i++)
    {
        int x, t; fin>>t;
        if(t == 1)
        {
            fin>>x;
            nr++, lg++;

            poz[nr] = lg; // poz in heap
            v[nr] = x;
            h[lg] = nr;

            push(lg);
        }
        else if(t == 2)
        {
            fin>>x;
            v[x] = -1;
            push(poz[x]);

            poz[h[1]] = 0;
            h[1] = h[lg--];
            poz[h[1]] = 1;

            if(lg > 1) pop(1);
        }
        else
            fout<<v[h[1]]<<'\n';
    }
    return 0;
}