#include <fstream>
#define MAX_SIZE 200010
#define INF 0x3f3f3f3f

using namespace std;

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

int H[MAX_SIZE], Pos[MAX_SIZE], A[MAX_SIZE], i, x, code, nr, N, length;

void swap (int &a, int &b) {
    int tmp = a;
    a = b;
    b = tmp;
}
inline int father(int node) {
    return node >> 1;
}
inline int left_son(int node) {
    return node << 1;
}
inline int right_son(int node) {
    return ((node << 1) + 1);
}
inline void push(int x) {
    while(father(x) && A[H[x]] < A[H[father(x)]]) {
        swap(H[x], H[father(x)]);

        Pos[H[x]] = x;
        Pos[H[father(x)]] = father(x);
        x /= 2;
    }
}
inline void pop (int x) {
    int y = 0;
    while(x != y) {
        y = x;
        if (y*2 <= length && A[H[x]] > A[H[y * 2]]) {
            x = y*2;
        }
        if (y * 2 + 1 <= length && A[H[x]] > A[H[y * 2 + 1]]) {
            x = y*2+1;
        }
        swap(H[x], H[y]);

        Pos[H[x]] = x;
        Pos[H[y]] = y;
    }
}
int main()
{
    f >> N;

    for(i = 1; i <= N; i++) {
        f >> code;
        if(code < 3) {
            f >> x;
        }

        if(code == 1) {
            length++;
            nr++;

            A[nr] = x;
            H[length] = nr;
            Pos[nr] = length;

            push(length);
        }
        if(code == 2) {
            A[x] = -INF;
            push(Pos[x]);
            Pos[H[1]] = 0;
            H[1] = H[length--];
            Pos[H[1]] = 1;
            if(length > 1) {
                pop(1);
            }
        }
        if(code == 3) {
            g << A[H[1]] << '\n';
        }
    }
    return 0;
}