#include <iostream>
#include <fstream>

using namespace std;

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

const int NMax = 2e5;

int L, NR;
int A[NMax], Heap[NMax], Pos[NMax];

void push(int node){
    int aux;
    while(node / 2 && A[Heap[node]] < A[Heap[node / 2]]){
        aux = Heap[node];
        Heap[node] = Heap[node / 2];
        Heap[node / 2] = aux;
        Pos[Heap[node]] = node;
        Pos[Heap[node / 2]] = node / 2;
        node /= 2;
    }
}

void pop(int node){
    int aux, y;
    y = 0;
    while(node != y){
        y = node;
        if(2 * y <= L && A[Heap[node]] > A[Heap[2 * y]]) node = 2 * y;
        if(2 * y + 1 <= L && A[Heap[node]] > A[Heap[2 * y + 1]]) node = 2 * y + 1;
        aux = Heap[node];
        Heap[node] = Heap[y];
        Heap[y] = aux;
        Pos[Heap[node]] = node;
        Pos[Heap[y]] = y;
    }
}

int main(){
    int n, x, cod;
    fin >> n;
    for(int i = 1; i <= n; i++){
        fin >> cod;
        if(cod < 3){
            fin >> x;
        }
        if(cod == 1){
            L++; NR++;
            A[NR] = x;
            Heap[L] = NR;
            Pos[NR] = L;
            push(L);
        }
        if(cod == 2){
            A[x] = -1;
            push(Pos[x]);
            Pos[Heap[1]] = 0;
            Heap[1] = Heap[L--];
            Pos[Heap[1]] = 1;
            if(L > 1){
                pop(1);
            }
        }
        if(cod == 3){
            fout << A[Heap[1]] << "\n";
        }
    }
    return 0;
}