#include <fstream>

using namespace std;
ifstream cin ("heapuri.in");
ofstream cout ("heapuri.out");
int n,v[200010],m,nr[200010],pozt[200001],o,v1[200010],y;
void climb (int x,int ppoozz)
{ int poz=ppoozz;
    while(3>2)
    {
        if( x < v[poz/2] && poz>1 )
            v[poz]=v[poz/2], v1[poz]=v1[poz/2], pozt[v1[poz]]=poz, poz/=2;
               else {v[poz]=x; v1[poz]=y;  pozt[y]=poz; break;}
    }
}
void down (int x,int ppoozz)
{ int w=v[x],poz;
    while(3>2)
    {
        if ( v[2*x]>v[2*x+1] && 2*x+1<=m ) poz=2*x+1; else if(2*x<=m) poz=2*x;
        if(w>v[poz] && 2*x<=m)
            v[x]=v[poz],x=poz,v1[x]=v1[poz],pozt[v1[x]]=x;
        else {v[x]=w; v1[x]=y; pozt[y]=x; break;}
    }
}
void read ()
{ int p,x;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>p;
        if(p==1)
        {
            cin>>x;nr[++o]=x;
            v[++m]=x; y=v1[m]=o;
            climb(x,m);
        }
        else if(p==2)
        {
            cin>>x; int poz=v1[m];
           v[pozt[x]]=v[m]; y=v1[pozt[x]]=v1[m]; pozt[poz]=pozt[x]; m--;
            climb(v[pozt[x]],pozt[x]);
            down(pozt[x],x); pozt[x]=0;
        }
        else cout<<v[1]<<"\n";
    }
}
int main()
{
    read();
    cin.close();
    cout.close();
    return 0;
}