#include <bits/stdc++.h>

using namespace std;

#define     mp              make_pair
#define     fs              first
#define     sc              second
#define     pob             pop_back
#define     pub             push_back
#define     eps             1E-7
#define     sz(a)           a.size()
#define     count_one       __builtin_popcount;
#define     count_onell     __builtin_popcountll;
#define     fastIO          ios_base::sync_with_stdio(false)
#define     PI              (acos(-1.0))
#define     linf            (1LL<<62)//>4e18
#define     inf             (0x7f7f7f7f)//>2e9

#define DEBUG 1
#ifdef DEBUG
#define D(x) x
#else
#define D(x)
#endif

#define MAXN    200020

FILE *in = fopen("heapuri.in", "r");
FILE *out = fopen("heapuri.out", "w");

int n, k = 0;
int inv[MAXN], h[MAXN], pos[MAXN];
//set<int, less<int>> in1;

inline int father(int nod) {
    return (nod >> 1);
}

inline int leftChild(int nod) {
    return (nod << 1);
}

inline int rightChild(int nod) {
    return (nod << 1) + 1;
}

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

void downHeap(int nod) {
    int son;
    do {
        son = 0;
        if(leftChild(nod) <= n) {
            son = leftChild(nod);
            if(rightChild(nod) <= n && h[rightChild(nod)] < h[leftChild(nod)])
                son = rightChild(nod);

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

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

int main()
{
    int type, x, y;
    fscanf(in, "%d", &n);

    for(int i = 1; n; n--) {
        fscanf(in, "%d", &type);
//        switch(type) {
//            case 1:
//                fscanf(in, "%d", &x);
//                in1.insert(x);
//                inv[i] = x;
//                i++;
//            break;
//
//            case 2:
//                fscanf(in, "%d", &x);
//                in1.erase(inv[x]);
//            break;
//
//            case 3:
//                fprintf(out, "%d\n", *(in1.begin()));
//            break;
//        }
        switch(type) {
            case 1:
                fscanf(in, "%d", &x);
                h[++k] = x;
                inv[i] = k;
                pos[k] = i;
                i++;
                upHeap(k);
            break;

            case 2:
                fscanf(in, "%d", &x);
                y = inv[x];
                h[y] = h[k];
                inv[pos[n]] = y;
                pos[y] = pos[n];
                --k;
                if( y > 1 && h[y] < h[father(y)])
                    upHeap(y);
                else
                    downHeap(y);
            break;

            case 3:
                fprintf(out, "%d\n", h[1]);
            break;
        }
    }

    return 0;
}