//minheap
 
#include<cstdio>
#include<algorithm>
 
#define MAX_SIZE 200005
 
FILE *f=fopen("heapuri.in","r");
FILE *g=fopen("heapuri.out","w");
 
 
using namespace std;
 
int n,l,nr,tip;
int heap[MAX_SIZE],v[MAX_SIZE],pos[MAX_SIZE];
 
void insert ( int node )
{
    int value=v[node];
    int p=heap[node];
 
     while( node/2>=1 && value < v[node/2]  )
     {
         pos[heap[node/2]]=node;
         heap[node]=heap[node/2];
         v[node]=v[node/2];
         node/=2;
          
     }
     pos[p]=node;
     heap[node]=p;
     v[node]=value;
      
}
void build ( int node )
{
 
    int nodeleft,noderight;
    int MIN;
    while(2*node <= l)
    {
      nodeleft=node<<1;
      noderight=nodeleft|1;
      MIN=node;
       if(v[nodeleft] < v[node ] ) MIN=nodeleft;
       if(  v[noderight] < v[MIN] ) MIN=noderight;
      if( MIN == node )
          break;
      else
      {
          int aux;
        swap(heap[node],heap[MIN]);
        swap(v[node],v[MIN]);
        pos[heap[MIN]]=MIN;
        pos[heap[node]]=node;
        node=MIN;
      }
    }
}
 
int main( void )
{
    fscanf(f,"%d",&n);
    int numb;
    int x;
    for(int i(1); i<= n ;++i )
    {
        fscanf(f,"%d",&tip);
        if( tip == 1)
 
        {
            fscanf(f,"%d",&x);
            l++,nr++;
            heap[l]=nr;
            v[l]=x;
            insert(l);
            continue;
        }
        if( tip == 2)
        {
            fscanf(f,"%d",&x);
                  
            heap[pos[x]]=heap[l];
             
            pos[heap[l]]=pos[x];
             
            v[pos[x]]=v[l];
             
            l--;
             
            if( v[pos[x]] < v[ pos[x]/2] )
                insert(pos[x]);
            else
                build(pos[x]);
 
           continue;
 
        }
        if ( tip == 3)
        {
            fprintf(g,"%d\n",v[1]);
        }
     }
 
   fclose(f);
   fclose(g);
   return 0;
}