#include <fstream>

using namespace std;

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

int n, k, nr;
int A[200010], Heap[200010], Pos[200010];

void push(int x)
{
    int aux;

    while (x/2 && A[Heap[x]]<A[Heap[x/2]])
    {
        aux = Heap[x];
        Heap[x] = Heap[x/2];
        Heap[x/2] = aux;

        Pos[Heap[x]] = x;
        Pos[Heap[x/2]] = x/2;
        x /= 2;
    }
}

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

    while (x != y)
    {
        y = x;

        if (y*2<=k && A[Heap[x]]>A[Heap[y*2]]) x = y*2;
        if (y*2+1<=k && A[Heap[x]]>A[Heap[y*2+1]]) x = y*2+1;

        aux = Heap[x];
        Heap[x] = Heap[y];
        Heap[y] = aux;

        Pos[Heap[x]] = x;
        Pos[Heap[y]] = y;
    }
}

int main()
{int i, x, op;


    fin >> n;
    for ( i = 1; i <= n; i++ )
    {
        fin >> op;
        if (op < 3)
        {
            fin >> x;
        }
        if ( op == 1)
        {
            k++, nr++;
            A[nr] = x;
            Heap[k] = nr;
            Pos[nr] = k;

            push(k);
        }

        if (op == 2)
        {
            A[x] = -1;
            push(Pos[x]);

            Pos[Heap[1]] = 0;
            Heap[1] = Heap[k--];
            Pos[Heap[1]] = 1;
            if (k>1) pop(1);
        }

        if (op == 3) fout<<A[Heap[1]]<<"\n";
    }

    return 0;
}