#include <iostream>
#include <fstream>

#define NMAX 200005

using namespace std;

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

int N;
int Heap[NMAX], Pos[NMAX], A[NMAX];
int L;

void Push(int x)
{
    while(x/2 && A[Heap[x]] < A[Heap[x/2]])
    {
        swap(Heap[x], Heap[x/2]);
        Pos[Heap[x]] = x;
        Pos[Heap[x/2]] = x/2;

        x /= 2;
    }
}

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

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

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

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

void Read()
{
    fin>>N;
    int cod;
    int x;
    int NR=0;
    for(int i=1;i<=N;i++)
    {
        fin>>cod;
        if (cod != 3)
        {
            fin>>x;

            if (cod == 1)
            {
                L++;
                NR++;
                A[NR] = x;
                Heap[L] = NR;
                Pos[NR] = L;

                Push(L);
            }
            else
            {
                A[x] = -1;
                Push(Pos[x]);
                Pos[Heap[1]] = 0;
                Heap[1] = Heap[L--];
                Pos[Heap[1]] = 1;
                if (L > 1)
                    Pop(1);
            }
        }
        else
        {
            fout<<A[Heap[1]]<<'\n';
        }
    }
}

int main()
{
    Read();
    return 0;
}