#include <bits/stdc++.h>

using namespace std;

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

const int N_MAX = 2e5+100;

#define FN (nod >> 1)                   /// father
#define LC (nod << 1)                   /// left child
#define RC (nod << 1) + 1               /// right child

int n, k;
int h[N_MAX], pos[N_MAX], inv[N_MAX];

void upHeap(int nod) {
    while(nod > 1 && h[FN] > h[nod]) {
        swap(h[FN], h[nod]);
        swap(pos[FN], pos[nod]);
        swap(inv[pos[FN]], inv[pos[nod]]);
        nod = FN;
    }
}

void downHeap(int nod) {
    int son;
    do {
        son = 0;
        if(LC <= k) {
            son = LC;
            if(RC <= k && h[RC] < h[son])
                son = RC;

            if(h[son] >= h[nod])
                son = 0;
        }

        if(son) {
            swap(h[son], h[nod]);
            swap(pos[son], pos[nod]);
            swap(inv[pos[son]], inv[pos[nod]]);
            nod = son;
        }
    } while(son);
}

int main() {
    fin >> n;
    k = 0;

    int t, x, y;
    for(int i = 1; n; --n) {
        fin >> t;
        if(t == 1) {
            fin >> h[++k];
            pos[k] = i;
            inv[i] = k;
            ++i;
            upHeap(k);
        }
        if(t == 2) {
            fin >> x;
            y = inv[x];
            h[y] = h[k];
            inv[pos[k]] = y;
            pos[y] = pos[k];
            --k;
            if(y > 1 && h[y] < h[(y >> 1)])
                upHeap(y);
            else
                downHeap(y);
        }
        if(t == 3) {
            fout << h[1] << "\n";
        }
    }
}