#include <fstream>
#define nmax 200010
using namespace std;
ifstream in("heapuri.in");
ofstream out("heapuri.out");
int N, L, NR, A[nmax], Heap[nmax], Pos[nmax];

void push(int nod)
{
    while(nod > 1 && A[Heap[nod]] < A[Heap[nod/2]])
    {
        swap(Heap[nod], Heap[nod/2]);
        Pos[Heap[nod]] = nod;
        Pos[Heap[nod/2]] = nod/2;
        nod /= 2;
    }
}

void pop(int nod)
{
    int y = 0;
    while(nod != y)
    {
        y = nod;

        if(y+y <= L && A[Heap[nod]] > A[Heap[y+y]]) nod = y+y;
        if(y+y+1 <= L && A[Heap[nod]] > A[Heap[y+y+1]]) nod = y+y+1;

        swap(Heap[nod], Heap[y]);

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

int main()
{
    in >> N;
    for(int t, x; N; N--)
    {
        in >> t;
        if(t != 3) in >> x;
        if(t == 1)
        {
            L++, NR++;
            A[NR] = x;
            Heap[L] = NR;
            Pos[NR] = L;
            push(L);
        }
        if(t == 2)
        {
            A[x] = -1;
            push(Pos[x]);

            Pos[Heap[1]] = 0;
            Heap[1] = Heap[L--];
            Pos[Heap[1]] = 1;
            if(L>1) pop(1);
        }
        if(t == 3)
            out << A[Heap[1]] << '\n';
    }
    return 0;
}