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

using namespace std;

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

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

void upHeap(int node)
{
    int T = node / 2;
    if (T > 0)
    {
        if (Heap[node] < 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 (Heap[node] > Heap[leftSon])
            son = leftSon;

        if (rightSon <= lgHeap)
        {
            if (Heap[son] > 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;
    Heap[0] = -1;

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

            Heap[++lgHeap] = x;
            val[++cnt] = x;
            if (!pos[x])
                pos[x] = lgHeap;

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

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

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