#include <cstdio>
#include <utility>
#define val first
#define pos second
using namespace std;
int nr,n;
pair <int,int> chronological[200001],heap[200001];

int push(int p)
{
   while(p>1 && heap[p].val<heap[p/2].val)
   {
      chronological[heap[p/2].pos].pos=p;
      chronological[heap[p].pos].pos=p/2;
      pair<int,int> aux=heap[p];
      heap[p]=heap[p/2];
      heap[p/2]=aux;
      p/=2;
   }
   return p;
}

void pull(int p)
{
   while(1)
   {
      int f=p;
      if(p*2<=n && heap[f].val>heap[p*2].val) f=p*2;
      if(p*2+1<=n && heap[f].val>heap[p*2+1].val) f=p*2+1;
      if(f==p)
         break;
      chronological[heap[f].pos].pos=p;
      chronological[heap[p].pos].pos=f;
      pair<int,int> aux=heap[p];
      heap[p]=heap[f];
      heap[f]=aux;
      p=f;
   }
}

int main()
{
   int q,x,p,c,i,j;
   int ct=0,aux;
   freopen("heapuri.in","r",stdin);
   freopen("heapuri.out","w",stdout);
   scanf("%d",&q);
   for(i=1; i<=q; i++)
   {
      scanf("%d",&c);
      if(c==1)
      {
         scanf("%d",&x);
         nr++;
         heap[++n]={x,nr};
         p=push(n);
         chronological[nr]={x,p};
         continue ;
      }
      if(c==2)
      {
         scanf("%d",&x);
         p=chronological[x].pos;
         chronological[heap[n].pos].pos=p;
         chronological[heap[p].pos].pos=n;
         pair<int,int> aux=heap[p];
         heap[p]=heap[n];
         heap[n]=aux;
         n--;
         if(heap[p].val<heap[p/2].val)
            push(p);
         else
            pull(p);
         continue ;
      }
      printf("%d\n",heap[1].first);
   }

   return 0;
}