#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){
            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>1 && 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){
    --len;
    while (node<=len){
        if (heap[2*node]==0 && heap[2*node+1]==0) break;
        if (heap[2*node]>heap[2*node+1]){
            swap(heap[node],heap[2*node]);
            pos[heap[node]]=node;
            pos[heap[2*node]]=2*node;
            node=2*node;
        } else {
            swap(heap[node],heap[2*node+1]);
            pos[heap[node]]=node;
            pos[heap[2*node+1]]=2*node+1;
            node=2*node+1;
        }
    }
}