#include <bits/stdc++.h>
using namespace std;

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

const int nmax = 2e5 + 5;
int n, heap[nmax], poz[nmax], v[nmax];

void percolate(int total, int k, int pos) {
    int key = v[k];
    while (k > 1 && key < v[k / 2]) {
        v[k] = v[k / 2];
        poz[k] = poz[k / 2];
        heap[poz[k]] = k;

        k = k / 2;
    }

    v[k] = key;
    poz[k] = pos;
    heap[pos] = k;
    return;
}

void sift(int total, int k, int pos) {
    int son;
    do {
        son = 0;
        if (k * 2 <= total) {
            son = k * 2;
            if (k * 2 + 1 <= total && v[k * 2 + 1] < v[2 * k])
                son = k * 2 + 1;

            if (v[son] >= v[k])
                son = 0;
            }


        if (son) {
            swap(v[k], v[son]);
            swap(heap[poz[k]], heap[poz[son]]);
            swap(poz[k], poz[son]);
            k = son;
        }

    }while(son);
}

int main()
{
    fin >> n;
    int total = 0, f = 0;
    for (int i = 1; i <= n; ++i) {
        int nr;
        fin >> nr;
        if (nr == 1) {
            int x;
            fin >> x;
            ++total, ++f;
            v[total] = x;
            heap[f] = total;
            poz[total] = f;
            percolate(total, total, f);
        }

        else if (nr == 2) {
            int pos;
            fin >> pos;
            v[heap[pos]] = v[total];
            poz[heap[pos]] = poz[total];
            heap[poz[total]] = heap[pos];
            --total;

            if (pos > 1 && v[heap[pos]] < v[heap[pos] / 2])
                percolate(total, heap[pos], poz[heap[pos]]);
            else
                sift(total, heap[pos], poz[heap[pos]]);
        }
        else fout << v[1] << '\n';
    }
    return 0;
}