#include <cstdio>
using namespace std;
FILE *fin=fopen("heapuri.in","r");
FILE *fout=fopen("heapuri.out","w");
#define NMAX 200005
#define ll long long
int k,poz[NMAX];
struct Heap {
int x,key;	
} H[NMAX];
void swap(Heap &x,Heap &y)
 {
 Heap ax=y;
 y=x;
 x=ax;
 }
void upheap(int i)
 {
 if(i>1)
  {
  if(H[i/2].x>H[i].x)
   {
   swap(H[i/2],H[i]);
   poz[H[i/2].key]=i/2;
   poz[H[i].key]=i;
   upheap(i/2);
   }
  }
 }
void dwheap(int i)
 {
 if(2*i<=k)
  {
  int y=2*i;
  if(y+1<=k&&H[y+1].x<H[y].x)
   ++y;
  swap(H[y],H[i]);
  poz[H[y].key]=y;
  poz[H[i].key]=i;
  dwheap(y);
  }
 }
int main()
 {
 int n,i,caz,nm=0,x,c;
 fscanf(fin,"%d",&n);
 for(i=1;i<=n;i++)
  {
  fscanf(fin,"%d",&caz);
  if(caz==1)
   {
   fscanf(fin,"%d",&H[++k].x);
   H[k].key=(++nm);
   poz[H[k].key]=k;
   upheap(k);
   }
  else if(caz==2)
   {
   fscanf(fin,"%d",&x);
   swap(H[k],H[poz[x]]);
   c=poz[x];
   poz[H[k].key]=k;
   poz[H[x].key]=x;
   --k;
   upheap(c);
   dwheap(c);
   }
  else
   fprintf(fout,"%d\n",H[1].x);
  }
 }