#include<stdio.h>
#include<string.h>
long h[200000],n,a[200000],hp[200000],ll,lh,i,p,aa;
void pune(long A)
{long hh;
while(A/2&&a[h[A]]<a[h[A/2]]&&a[h[A]]>0)
 {hh=h[A];h[A]=h[A/2];h[A/2]=hh;
  hp[h[A]]=A;hp[h[A/2]]=A/2;A/=2;}
}
void ia(long A)
{long hh,aa;
 while(A!=aa)
  {aa=A;
   if(aa*2<=lh&&a[h[A]]>a[h[aa*2]])A=aa*2;
   if(aa*2+1<=lh&&a[h[A]]>a[h[aa*2+1]])A=aa*2+1;
   hh=h[A];h[A]=h[aa];h[aa]=hh;
   hp[h[A]]=A;hp[h[aa]]=aa;
  }
}
/*void CombHeap(long i,long n)
{long v=h[i],tata=i,fiu=2*i;
while(fiu<=n)
{if(fiu<n)
   if(h[fiu]>h[fiu+1])++fiu;
 if(v>h[fiu])
   {h[tata]=h[fiu];
    tata=fiu;
    fiu*=2;}
    else
     fiu=n+1;}
h[tata]=v;}
void CreareHeap(long n)
{
 long i;
 for(i=n/2;i;--i)
    CombHeap(i,n);
}  */
int main()
{
 freopen("heapuri.in","r",stdin);
 freopen("heapuri.out","w",stdout);
 scanf("%ld",&n);
 for(i=1;i<=n;++i)
    {scanf("%ld",&p);
     if(p<3)scanf("%ld",&aa);
     if(p==1){++ll;++lh;a[ll]=aa;h[lh]=ll;hp[ll]=lh;pune(lh);}
     if(p==2){
      a[aa]=-1;
      pune(hp[aa]);
      h[hp[aa]]=h[lh--];
      hp[aa]=1;
      if(lh>1)ia(1);}
     if(p==3){printf("%ld\n",a[h[1]]);}
    }
 return 0;
}