#include <iostream>
#include <fstream>
#include <unordered_set>
using namespace std;
ifstream fin("heapuri.in");
ofstream fout("heapuri.out");
int v[200010], loc[200010], heap[200010];
void climb_up(int poz)
{
    while(poz/2 && v[heap[poz]] < v[heap[poz / 2]])
    {
        swap(heap[poz], heap[poz / 2]);
        loc[heap[poz]] = poz;
        loc[heap[poz / 2]] = poz / 2;
        poz = poz / 2;
    }
}
void climb_down(int poz, int nr)
{
    int son = -1;
    while(son != poz)
    {
        son = poz;
        int l = 2*poz;
        int r = 2*poz+1;
        if(l <= nr && v[heap[l]] < v[heap[poz]])
            poz = l;
        if(r <= nr && v[heap[r]] < v[heap[poz]])
            poz = r;

        swap(heap[poz], heap[son]);
        loc[heap[poz]] = poz;
        loc[heap[son]] = son;
    }
}
int main()
{
    int n, op, x, num_elem = 0, nr = 0;
    v[0] = -1;
    fin >> n;
    for(int i = 1; i <= n; i++)
    {
        fin >> op;
        if(op == 1)
        {
            fin >> x;
            num_elem++;
            nr++;
            loc[num_elem] = nr;
            v[num_elem] = x;
            heap[nr] = num_elem;
            climb_up(nr);
        }
        else if (op == 2)
        {
            fin >> x;
            swap(heap[loc[x]], heap[nr]);
            loc[heap[loc[x]]] = loc[x];
            nr--;
            climb_up(loc[x]);
            climb_down(loc[x], nr);
        }
        else
        {
            fout << v[heap[1]] << '\n';
        }
    }
    return 0;
}