#include <fstream>
#define DIM 500010
using namespace std;

ifstream fin ("heapuri.in" );
ofstream fout("heapuri.out");

int n, m, i, j, k, ok, minim, x, y;
int v[DIM], t, h, w[DIM], l;

int cond_1(){return x == 3;}
int cond_2(){return x == 1;}
int cond_3(){return x == 2;}

void swap(int a, int b){
     int c;
     c = v[a]; v[a] = v[b]; v[b] = c;
     c = w[a]; w[a] = w[b]; w[b] = c;
     return;
}

void Build_Heap(){
     fin >> n;
     for(h = 1; h <= n; h ++){
          fin >> x;
          if(cond_1()){
               fout << v[1] << "\n";
          }
          if(cond_2()){
               fin >> y; k ++;
               v[k] = y; w[k] = ++l;
               t = k;
               ok = 1;
               while(ok == 1){
                    if(v[t] < v[t/2] && t != 1)
                         swap(t, t/2);
                    else
                         ok = 0;
                    t /= 2;
               }
          }
          if(cond_3()){
               fin >> y; i = 1;
               while(w[i] != y) i ++;
               v[i] = v[k]; w[i] = w[k];
               v[k] = 0; w[k] = 0; k --;
               t = i; ok = 1;
               if(v[t] < v[t/2]){
                    while(ok == 1){
                         if(v[t] < v[t/2] && t != 1)
                              swap(t, t/2);
                         else
                              ok = 0;
                         t /= 2;
                    }
               }
               else{
                    while(ok == 1){
                         if(v[t*2] == 0)
                              break;
                         if(v[t] > v[t*2] && t <= k)
                              swap(t, t*2);
                         else
                              ok = 0;
                         t *= 2;
                    }
                    t = i; ok = 1;
                    while(ok == 1){
                         if(v[t*2+1] == 0)
                              break;
                         if(v[t] > v[t*2+1] && t <= k)
                              swap(t, t*2+1);
                         else
                              ok = 0;
                         t *= 2;
                    }
               }
          }
     }
     return;
}

int main(){
     Build_Heap();
     return 0;
}