#include<stdio.h>
#define nmax 200005
int a[nmax],pos[nmax],heap[nmax],L,NR,N;

void push (int x)
 {
  int aux;
  while (x/2 && a[heap[x]]<a[heap[x/2]])
   {
    aux=heap[x];
    heap[x]=heap[x/2];
    heap[x/2]=aux;
    pos[heap[x]]=x;
    pos[heap[x/2]]=x/2;
    x>>=1;
   }
 }

void pop (int x)
 {
  int y=0,aux;
  while (x!=y)
   {
    y=x;
    if (y*2<=L && a[heap[x]]>a[heap[y*2]])
      x=y*2;
    if (y*2+1<=L && a[heap[x]]>a[heap[y*2+1]])
      x=y*2+1;
    aux=heap[x];
    heap[x]=heap[y];
    heap[y]=aux;
    pos[heap[x]]=x;
    pos[heap[y]]=y;
   }
 }

int main()
 {
  freopen("heapuri.in","r",stdin);
  freopen("heapuri.out","w",stdout);
  scanf("%d",&N);
  int i,c,x;
  for (i=1;i<=N;++i)
   {
    scanf("%d",&c);
    if (c!=3)
      scanf("%d",&x);
    if (c==1)
     {
      ++L,++NR;
      a[NR]=x;
      heap[L]=NR;
      pos[NR]=L;
      push(L);
     }
    if (c==2)
     {
      a[x]=-1;
      push(pos[x]);
      pos[heap[1]]=0;
      heap[1]=heap[L--];
      pos[heap[1]]=1;
      if (L>1)
	pop(1);
     }
    if (c==3)
      printf ("%d\n",a[heap[1]]);
   }
  return 0;
 }