//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;
}