#include <fstream>
#include <cstring>

#define MAX 200001
#define BIN 262145

using namespace std;

int Heap[BIN],v[MAX],pos[MAX];
int size=0,cnt=0;

inline void HeapUp(int nod)
{
    int ind=Heap[nod];

    while(nod>1&&v[ind]<v[Heap[nod>>1]])
    {
        Heap[nod]=Heap[nod>>1];
        pos[Heap[nod]]=nod;
        nod>>=1;
    }

    Heap[nod]=ind;
    pos[ind]=nod;
}

inline void HeapDown(int nod)
{
    int Down=0,x,y,ind=Heap[nod];

    x=nod<<1;
    y=(nod<<1)+1;

    if(y<BIN&&Heap[y]) Down=2;
    else
    if(x<BIN&&Heap[x]) Down=1;

    while(Down)
    {
        if(Down==2)
        {
            if(v[Heap[x]]<v[Heap[y]])
            {
                if(v[ind]>v[Heap[x]])
                {
                    Heap[nod]=Heap[x];
                    pos[Heap[nod]]=nod;
                    nod=x;
                }
                else
                {
                    Heap[nod]=ind;
                    pos[ind]=nod;
                    return;
                }
            }
            else
            {
                if(v[ind]>v[Heap[y]])
                {
                    Heap[nod]=Heap[y];
                    pos[Heap[nod]]=nod;
                    nod=y;
                }
                else
                {
                    Heap[nod]=ind;
                    pos[ind]=nod;
                    return;
                }
            }
        }
        else
        if(Down==1)
        {
            if(v[ind]>v[Heap[x]])
            {
                Heap[nod]=Heap[x];
                pos[Heap[nod]]=nod;
                nod=x;
            }
            else
            {
                Heap[nod]=ind;
                pos[ind]=nod;
                return;
            }
        }
        else
        {
            Heap[nod]=ind;
            pos[ind]=nod;
            return;
        }

        Down=0;
        x=nod<<1;
        y=(nod<<1)+1;

        if(y<BIN&&Heap[y]) Down=2;
        else
        if(x<BIN&&Heap[x]) Down=1;
    }

    Heap[nod]=ind;
    pos[ind]=nod;
}

inline void Cut(int K)
{
    pos[Heap[cnt]]=pos[Heap[K]];
    Heap[K]=Heap[cnt];
    Heap[cnt]=0;

    if(K!=cnt)
    {
        if(K>1&&v[Heap[K]]<v[Heap[K>>1]]) HeapUp(K);
        else HeapDown(K);
    }

    cnt--;
}

int main()
{
    int N,x;

    ifstream in;
    ofstream out;

    in.open("heapuri.in");
    out.open("heapuri.out");

    in>>N;
    for(;N;--N)
    {
        in>>x;
        if(x==2)
        {
            in>>x;
            Cut(pos[x]);
        }
        else
        if(x==1)
        {
            in>>v[++size];
            Heap[++cnt]=size;
            HeapUp(cnt);
        }
        else out<<v[Heap[1]]<<'\n';
    }

    in.close();
    out.close();

    return 0;
}