#include <iostream>
#include <fstream>

#define maxn 200010

using namespace std;

int N,l,sz;
int a[maxn], heap[maxn], poz[maxn];

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

void push(int x)
{
    int aux;
    while (x/2 && a[heap[x]] < a[heap[x/2]])
    {
        aux = heap[x];
        heap[x] = heap[x/2];
        heap[x/2] = aux;
        poz[heap[x]] = x;
        poz[heap[x/2]] = x/2;
        x = x/2;
    }
}

void pop(int x)
{
    int aux, 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;
        aux = heap[x];
        heap[x] = heap[y];
        heap[y] = aux;
        poz[heap[x]] = x;
        poz[heap[y]] = y;
    }
}

int main()
{
    fin>>N;
    for (int i = 1; i <= N; i++)
    {
        int c, x;
        fin >> c;
        if (c < 3) fin >> x;
        if (c == 1)
        {
            l++;
            sz++;
            a[sz] = x;
            heap[l] = sz;
            poz[sz] = l;
            push(l);
        }
        if (c == 2)
        {
            a[x] = -1;
            push(poz[x]);
            poz[heap[1]] = 0;
            heap[1] = heap[l--];
            poz[heap[1]] = 1;
            if (l > 1) pop(1);
        }
        if (c == 3) fout<< a[heap[1]] << endl;
    }
    return 0;
}