#include <cstdio>
#include <algorithm>
#define v first
#define p second

using namespace std;
int q,k,i,n,t,x,y,b[200009],nr,copie;
pair <int,int> a[400009];

void HeUp(int poz)
{
   if(poz==1) return;
   if(a[poz/2].v>a[poz].v)
   {
      swap(a[poz],a[poz/2]);
      swap(b [a[poz].p ] , b [a[poz/2].p]);
      HeUp(poz/2);
   }
}

void HeDw(int k,int n)
{
    if(2*k<=n && a[2*k].v<=a[2*k+1].v)
    {
        if(a[2*k].v<=a[k].v)
        {
            swap(a[k],a[2*k]);
            swap( b[a[k].p],b[a[2*k].p] );
            HeDw(2*k,n);
        }
    }
    else if(2*k+1<=n && a[2*k+1].v<a[2*k].v)
    {
        if(a[2*k+1].v<a[k].v)
        {
            swap(a[k],a[2*k+1]);
            swap(b[a[k].p],b[a[2*k+1].p]);
            HeDw(2*k+1,n);
        }
    }
    else if(n==2*k)
    {
         if(a[2*k].v<a[k].v)
        {
            swap(a[k],a[2*k]);
            swap(b[a[k].p],b[a[2*k].p]);
            HeDw(2*k,n);
        }
    }
}


int main()
{
    freopen("heapuri.in","r",stdin);
    freopen("heapuri.out","w",stdout);

    scanf("%d",&q);
    nr=0;y=0;
    for(i=1; i<=q; ++i)
    {
        scanf("%d",&t);
        if(t!=3) scanf("%d",&x);
        if(t==1)
        {
            a[++nr].v=x;++y;
            a[nr].p=y;
            b[y]=nr;
            HeUp(nr);
        }
        else if(t==2)
        {
            copie=b[x];
            swap(a[b[x]],a[nr]);
            swap(b[a[b[x]].p], b[a[nr].p] );

            HeDw(copie,nr-1);
            --nr;
        }
        else printf("%d\n",a[1].v);
    }
    return 0;
}