#include <fstream>
#include <cstring>

#define MAX 200001
#define BIN 262145

using namespace std;

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

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

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

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

inline void swap(int &a,int &b)
{
    int c=a;
    a=b;
    b=c;
}

inline void HeapDown(int nod,int cnt)
{
    int Down=0;
    if(H[2*nod+1]!=0) Down=2;
    else
    if(H[2*nod]!=0) Down=1;

    while(Down&&nod<cnt)
    {
        if(Down==1)
        {
            if(v[H[nod]]>v[H[2*nod]])
            {
                swap(H[nod],H[2*nod]);
                swap(pos[H[2*nod]],pos[H[nod]]);
                nod=2*nod;
            }
            else return;
        }

        if(Down==2)
        {
            if(v[H[2*nod]]<v[H[2*nod+1]])
            {
                if(v[H[nod]]>v[H[2*nod]])
                {
                    swap(H[nod],H[2*nod]);
                    swap(pos[H[2*nod]],pos[H[nod]]);
                    nod=2*nod;
                }
                else return;
            }
            else
            if(v[H[nod]]>v[H[2*nod+1]])
            {
                swap(H[nod],H[2*nod+1]);
                swap(pos[H[2*nod+1]],pos[H[nod]]);
                nod=2*nod+1;
            }
            else return;
        }

        Down=0;
        if(H[2*nod+1]!=0) Down=2;
        else
        if(H[2*nod]!=0) Down=1;
    }
}

inline void Cut(int K,int nod,int cnt)
{
    pos[H[nod]]=pos[H[K]];
    H[K]=H[nod];
    H[nod]=0;

    nod=K;

    if(nod>1&&v[H[nod>>1]]>v[H[nod]]) HeapUp(nod);
    else HeapDown(nod,cnt);
}

int main()
{
    int N,x,i;

    ifstream in;
    ofstream out;

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

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

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

    return 0;
}