#include <cstdio>
using namespace std;
FILE *fin=fopen("heapuri.in","r");
FILE *fout=fopen("heapuri.out","w");
#define NMAX 200005
int H[NMAX],k,i1[NMAX],i2[NMAX];
//i1[i] - pozitia din heap a elementului intrat a i-a oara, inversa functiei i2
//i2[i] - a cata oara este intrat elementul i din heap, inversa functiei i1
void swap(int &x,int &y)
 {
 int ax=x;
 x=y;
 y=ax;
 }
void upheap(int i)
 {
 if(i>1)
  {
  if(H[i/2]>H[i])
   {
   swap(H[i/2],H[i]);
   swap(i2[i/2],i2[i]);
   i1[i2[i/2]]=i/2;
   i1[i2[i]]=i;
   upheap(i/2);
   }
  }
 }
void dheap(int i)
 {
 if(2*i<=k)
  {
  int y=2*i;
  if(y+1<=k&&H[i+1]<H[i])
   ++y;
  if(H[i]>H[y])
   {
   swap(H[i],H[y]);
   swap(i2[i],i2[y]);
   i1[i2[i]]=i;
   i1[i2[y]]=y;
   dheap(y);
   }
  }
 }
int main() 
 {
 int n,x,op,i,ii=0,c;
 fscanf(fin,"%d",&n);
 for(i=1;i<=n;i++)
  {
  fscanf(fin,"%d",&op);
  if(op==1)
   {
   fscanf(fin,"%d",&x);
   H[++k]=x;
   i1[++ii]=k;
   i2[k]=ii;
   upheap(k);
   }
  else if(op==2)
   {
   fscanf(fin,"%d",&x);
   swap(H[k],H[i1[x]]);
   c=i1[x];
   swap(i2[k],i2[i1[x]]);
   i1[i2[i1[x]]]=i1[x];
   i1[i2[k]]=k;
   
   H[k]=0;
   --k;
   upheap(c);
   dheap(c);
   }
  else
   {
   fprintf(fout,"%d\n",H[1]);
   }
  }
 return 0;
 }