#include <iostream>
#include <fstream>
using namespace std;

#define maxN 200005

ifstream f("heapuri.in");
ofstream g("heapuri.out");

int n,k,nr;
int v[maxN],heap[maxN],poz[maxN];

void insert_elem(int x)
{
    int aux;

    while( x/2 && v[heap[x]] < v[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 delete_elem(int x)
{
    int aux, y = 0;

    while(x != y)
    {
        y = x;

        if( y*2<=k && v[heap[x]]>v[heap[y*2]]) x = y*2;
        if( y*2+1<=k && v[heap[x]]>v[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()
{
    int i,x,t;

    f>>n;

    for(i=1; i<=n; i++)
    {
        f>>t;

        if(t<3)
        {
            f>>x;
        }

        if(t==1)
        {
            k++; nr++;
            v[nr] = x;
            heap[k] = nr;
            poz[nr] = k;

            insert_elem(k);
        }

        if(t==2)
        {
            v[x] = -1;
            //assert(Pos[x] != 0);
            //assert(1<=x && x<=NR);
            insert_elem(poz[x]);

            poz[heap[1]] = 0;
            heap[1] = heap[k--];
            poz[heap[1]] = 1;
            if(k>1) delete_elem(1);
        }

        if(t==3) g<<v[heap[1]]<<endl;
    }

    return 0;
}