#include <bits/stdc++.h>
#define N 200005

using namespace std;

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

int n, lgHeap, Heap[N];
int pos[N];
int val[N], cnt;

void upHeap(int node)
{
    int T = node / 2;
    if (T > 0)
    {
        if (val[Heap[node]] < val[Heap[T]])
        {
            pos[Heap[node]] = T;
            pos[Heap[T]] = node;
            swap(Heap[node], Heap[T]);
            upHeap(T);
        }
    }
}

void downHeap(int node)
{
    int leftSon = 2 * node, rightSon = 2 * node + 1;
    int son = 0;
    if (leftSon <= lgHeap)
    {
        if (val[Heap[node]] > val[Heap[leftSon]])
            son = leftSon;

        if (rightSon <= lgHeap)
        {
            if (val[Heap[node]] > val[Heap[rightSon]])
                {
                    if (val[Heap[leftSon]] > val[Heap[rightSon]])
                        son = rightSon;
                }
        }

        if (son)
        {
            pos[Heap[node]] = son;
            pos[Heap[son]] = node;
            swap(Heap[node], Heap[son]);
            downHeap(son);
        }
    }
}

int main()
{
    fin >> n;
    val[Heap[0]] = -1;

    for (int i = 1; i <= n; i++)
    {
        int op;
        fin >> op;
        if (op == 1)
        {
            int x;
            fin >> x;

            val[++cnt] = x;
            Heap[++lgHeap] = cnt;
            pos[cnt] = lgHeap;

            upHeap(lgHeap);
        }
        else if (op == 2)
        {
            int x;
            fin >> x;

            int posHeap = pos[x];
            swap(Heap[posHeap], Heap[lgHeap--]);

            upHeap(posHeap);
            downHeap(posHeap);
        }
        else
            fout << val[Heap[1]] << "\n";

    }

    return 0;
}