#include <iostream>
#include <fstream>
//de ce dracu imi trebe sa implementez heap de mana...nu stiu.....
using namespace std;
const int Maxx=2e5+100;
ifstream fin("heapuri.in");
ofstream fout("heapuri.out");
int querry;
int cod,elem,poz,pz,i;
int len;
bool ok;
int heap[Maxx];
int pos[Maxx];
int A[Maxx],n;
void percolate(int node);
void shift(int node);
int cauta (int node,int poz);
int main() {
    fin>>querry;++querry;
    for(;--querry;){
        fin>>cod;
        if (cod==1){
            ++n;
            fin>>A[n];
            heap[++len]=n;
            pos[n]=len;
            percolate(len);
            continue;
        }
        if (cod==2) {
            fin>>poz;
            A[poz]=-1;
            percolate(pos[poz]);
            pos[heap[1]]=0;
            heap[1]=heap[len--];
            pos[heap[1]]=1;
            if (len>1) shift(1);
            continue;
        }
        fout<<A[heap[1]]<<"\n";
    }
    return 0;
}
void percolate(int node){
    while (node/2 && A[heap[node]]<A[heap[node/2]]){
        swap(heap[node],heap[node/2]);
        pos[heap[node]]=node;
        pos[heap[node/2]]=node/2;
        node/=2;
    }
}
void shift(int node){
    int son=0;
    while (node!=son){
        son=node;
        if (2*son<=len && A[heap[node]]>A[heap[2*son]]) node=2*son;
        if (2*son+1<=len && A[heap[node+1]]>A[heap[2*son+1]]) node=2*son+1;
        swap(heap[node],heap[son]);
        pos[heap[node]]=node;
        pos[heap[son]]=son;
    }
}