#include <bits/stdc++.h>

using namespace std;

ifstream f("heapuri.in");
ofstream g("heapuri.out");

const int NMAX = 200010;
int A[NMAX], Heap[NMAX], Pos[NMAX];
int n,L,nr;

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

        Pos[Heap[x]] = x;
        Pos[Heap[x / 2]] = x / 2;
        x /= 2;
    }
}

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

        aux = Heap[x];
        Heap[x] = Heap[y];
        Heap[y] = aux;

        Pos[Heap[x]] = x;
        Pos[Heap[y]] = y;
    }
}

int main(){
    int i,x,y;
    f >> n;
    for(i = 1 ; i <= n ; i++){
        f >> x;
        if(x < 3)
            f >> y;
        if(x == 1){
            L++;
            nr++;
            A[nr] = y;
            Heap[L] = nr;
            Pos[nr] = L;
            push(L);
        }else
            if(x == 2){
                A[y] = -1;
                push(Pos[y]);

                Pos[Heap[1]] = 0;
                Heap[1] = Heap[L--];
                Pos[Heap[1]] = 1;
                if(L > 1)
                    pop(1);
            }else
                g << A[Heap[1]] << "\n";
    }

    return 0;
}