#include <iostream>
#include<fstream>
using namespace std;
int x,y,i,H,j,p,q,k,n,v[200001],h[200001],poz[200001],p2[19];
void ad(int a,int p)
{
    v[p]=a;
    h[++H]=p;
    j=H;
    poz[p]=H;
    while(v[h[j]]<v[h[j/2]])
    {
        swap (h[j],h[j/2]);
        poz[h[j]]=j;
        poz[h[j/2]]=j/2;
        j=j/2;
    }
    //poz[p]=j;
}
void el(int p)
{
    j=poz[p];
    if(j<H)
    {
        poz[h[H]]=j;
        swap(h[j],h[H]);
        --H;
        while(v[h[j]]>v[h[2*j]])
            {
                swap(h[j],h[2*j]);
                poz[h[j]]=j;
                poz[h[2*j]]=2*j;
                j=j*2;
            }
    }
    else
        --H;
}
int main()
{
    ifstream f("heapuri.in");
    f>>q;
    ofstream g("heapuri.out");
    p2[0]=1;for(i=1;i<19;++i)p2[i]=2*p2[i-1];
    for(p=0;p<q;++p)
    {
        f>>x;//cout<<p<<'\n';
        if(x>2)
        {
            if(H<2)
            {
                g<<v[h[1]]<<'\n';
            }
            else
            {
                if(H<3)
                {
                    if(v[h[2]]<v[h[1]])g<<v[h[2]]<<'\n';
                    else
                        g<<v[h[1]]<<'\n';
                }
                else
                {
                    if(v[h[2]]<v[h[1]])
                    {
                        if(v[h[2]]<v[h[3]])g<<v[h[2]]<<'\n';
                        else
                            g<<v[h[3]]<<'\n';
                    }
                    else
                    {
                        if(v[h[1]]<v[h[3]])
                        {
                            g<<v[h[1]]<<'\n';
                        }
                        else
                        {
                            g<<v[h[3]]<<'\n';
                        }
                    }
                }
            }
        }
        else
        {
            f>>y;
            if(x<2)
            {
                ++n;
                ad(y,n);
            }
            else
            {
                //el(y);
                j=poz[y];
                if(j<H)
                {
                    poz[h[H]]=j;
                    swap(h[j],h[H]);
                    //--H;
                    while(v[h[j]]>v[h[2*j]]&&2*j<H)
                        {
                            swap(h[j],h[2*j]);
                            poz[h[j]]=j;
                            poz[h[2*j]]=2*j;
                            j=j*2;
                        }
                    --H;
                }
                else
                    --H;
            }
        }
    }
    f.close();
    g.close();
    return 0;
}