#include <iostream>
#include <fstream>
#define Nmax 200005

using namespace std;

ifstream f("heapuri.in");
ofstream g("heapuri.out");

int n;
int a[Nmax];
int h[Nmax]; // heap cu pozitiile elementelor din vectorul a
int p[Nmax]; // pozitia in heap a elementului i
int l, nr;

void push (int x)
{
    while (x/2!=0 && a[h[x]] < a[h[x/2]])
    {
        swap(h[x], h[x/2]);
        p[h[x]]=x;
        p[h[x/2]]=x/2;
        x/=2;
    }
}

void pop (int x)
{
    int y=0;

    while (x!=y)
    {
        y=x;
        if (y*2 <= l && a[h[x]] > a[h[2*y]]) x=2*y;
        if (y*2+1 <= l && a[h[x]] > a[h[2*y+1]]) x=2*y+1;
        swap(h[x], h[y]);
        p[h[x]]=x;
        p[h[y]]=y;
    }
}
/*
9
1 4
1 7
1 9
3
1 2
2 1
3
2 4
3
*/
int main()
{
    f >> n;
    int cod, x;
    while (n--)
    {
        f >> cod;
        if (cod == 1)
        {
            f >> x;

            l++, nr++;
            a[nr]=x;
            h[l]=nr;
            p[nr]=l;
            push(l);
           /* if (x == 2)
            {
                for (int i = 1; i <= l; i++) cout << a[i] << " "; cout << '\n';
                for (int i = 1; i <= l; i++) cout << h[i] << " "; cout << '\n';
                for (int i = 1; i <= l; i++) cout << p[i] << " "; cout << '\n';
            }*/
        }
        else if (cod == 2)
        {
            f >> x;
            a[x]=-1;
            push(p[x]);

            p[h[1]]=0; // daca p[i]=0 atunci a[i] este sters
            h[1]=h[l]; l--;
            p[h[1]]=1;
            if (l > 1) pop(1);

        }
        else if (cod == 3)
        {
            g << a[h[1]] << '\n';
        }
    }

    return 0;
}