#include <fstream>
#include <stdio.h>

using namespace std;
int heap [200002], ord[200002];
int n, cnt = 1, nr, lpos, i;

int parent (int n){
    return (n - 1) / 2;
}

int lchild (int n){
    return n * 2 + 1;
}
int rchild (int n){
    return n * 2 + 2;
}


void upHeap(int i) {
  while (i && heap[parent(i)] > heap[i]) {
    swap(heap[parent(i)], heap[i]);
    i = parent(i);
  }
}


void ReHeap(int i)
{
    int l = lchild(i);
    int r = rchild(i);
    int s = i;
    if (l < lpos && heap[l] < heap[i])
        s = l;
    if (r < lpos && heap[r] < heap[s])
        s = r;
    if (s != i)
    {
        swap(heap[i], heap[s]);
        ReHeap(s);
    }
}


int extract(int i)
{
    if (lpos == 1)
    {
        lpos--;
        return heap[0];
    }

    int root = heap[i];
    heap[i] = heap[lpos-1];
    lpos--;
    ReHeap(i);

    return root;
}
int findStuff(int i, int value){
    if (heap[0] == i)
        return 0;
    if (heap[value] == i)
        return value;
    int c = findStuff(i, lchild(value));
    if (c)
        return c;
    else
        return findStuff(i, lchild(value));

}


int main()
{
    ifstream in ("heapuri.in");
    ofstream out ("heapuri.out");


    int p;
    in >> n;
    for (i = 0; i < n; i ++){
        in >> p;
        if (p == 1){
            in >> nr;
            ord [cnt] = nr; cnt ++;
            heap [lpos] = nr; upHeap(lpos); lpos ++;
        }
        else if (p == 3)
            out << heap[0] << '\n';
        else if (p == 2){
            in >> nr;
            int x = findStuff(ord[nr], 0);
            extract (x);
        }
    }
    return 0;
}