//#include <iostream>
//#include <fstream>
//using namespace std;
//ifstream in("heapuri.in");
//ofstream out("heapuri.out");
//
//const int N = 200005;
//int val[N], heap[N], pos[N], n, op, arg, nh, t; //nh - number of nodes in the heap, t - the time of the last added item
//
//void moveUp(int poz) {
//    while(poz / 2 > 0 && val[heap[poz / 2]] > val[heap[poz]]) {
//        swap(heap[poz / 2], heap[poz]);
//        swap(pos[heap[poz]], pos[heap[poz / 2]]);
//        poz /= 2;
//    }
//}
//
//void moveDown(int poz) {
//    while(true) {
//        int child_pos1 = poz * 2, child_pos2 = child_pos1 + 1, min_child_pos = poz;
//        if(child_pos1 <= nh && val[heap[poz]] > val[heap[child_pos1]])
//            min_child_pos = child_pos1;
//        if(child_pos2 <= nh && val[heap[poz]] > val[heap[child_pos2]])
//            min_child_pos = child_pos2;
//
//        if(min_child_pos == poz)
//            break;
//
//        swap(heap[poz], heap[min_child_pos]);
//        swap(pos[heap[poz]], pos[heap[min_child_pos]]);
//    }
//}
//
//void push(int x) {
//    val[++ t] = x;
//    heap[++ nh] = t;
//    pos[t] = nh;
//    moveUp(nh);
//}
//
//void pop(int time) {
//    val[time] = -1;
//    moveUp(pos[time]);
//
//    pos[heap[1]] = 0;
//    heap[1] = heap[nh --];
//    pos[heap[1]] = 1;
//    if(nh > 1)
//        moveDown(1);
//}
//
////void test(){
////    ifstream in1("grader_test5.ok");
////    ifstream in2("heapuri.out");
////    int line = 0;
////    int x, y;
////    while(in1 >> x){
////        in2 >> y;
////        ++ line;
////        if(x != y){
////            cout << "NU " << line << endl;
////        }
////    }
////    cout << "\nDA";
////}
//
//int main() {
//    in >> n;
//    while(n --) {
//        in >> op;
//
//        if(op == 1) {
//            in >> arg;
//            push(arg);
//        }
//
//        else if(op == 2) {
//            in >> arg;
//            pop(arg);
//        }
//
//        else if(op == 3){
//            out << val[heap[1]] << '\n';
//        }
//    }
//
//    out.close();
////    test();
//
//    return 0;
//}

#include <fstream>
#include <vector>
#include <iostream>
#include <unordered_map>

using namespace std;
ifstream in("heapuri.in");
ofstream out("heapuri.out");

int n, op, ord = 0, pos, x;
vector<pair<int, int>> v;
unordered_map<int, int> add_time;

void moveUp(int posx) {
    while(posx / 2 > 0 && v[posx / 2].first > v[posx].first){
        swap(v[posx], v[posx / 2]);
        swap(add_time[v[posx].second], add_time[v[posx / 2].second]);
        posx /= 2;
    }
}

void solve1(){
    in >> x;
    v.emplace_back(x, ++ ord);
    int posx = (int)(v.size() - 1);
    add_time[ord] = posx;
    moveUp(posx);
}

void moveDown(int pos) {
    while(pos * 2 < (int)v.size()){
        int child_pos = 2 * pos;
        if(child_pos + 1 < (int)v.size())
            child_pos = (v[child_pos + 1].first < v[child_pos].first)? child_pos + 1 : child_pos;
        if(v[pos].first > v[child_pos].first) {
            swap(v[pos], v[child_pos]);
            swap(add_time[v[pos].second], add_time[v[child_pos].second]);
            pos = child_pos;
        }
        else
            break;
    }
}

void solve2(){
    in >> pos;
    pos = add_time[pos];
    v[pos].first = -1;
    moveUp(pos);
    swap(v[1], v[v.size() - 1]);
    swap(add_time[v[1].second], add_time[v[v.size() - 1].second]);
    add_time.erase(v[v.size() - 1].second);
    v.pop_back();
    moveDown(1);
}

//void test(){
//    ifstream in1("grader_test5.ok");
//    ifstream in2("heapuri.out");
//    int line = 0;
//    int x, y;
//    while(in1 >> x){
//        in2 >> y;
//        ++ line;
//        if(x != y){
//            cout << "NU " << line << '\n';
//        }
//    }
//    cout << "\nDA";
//}

int main() {
    v.emplace_back(-1, -1);
    in >> n;
    while(n --){
        in >> op;
        if(op == 1)
            solve1();
        else if(op == 2)
            solve2();
        else
            out << v[1].first << '\n';
    }
    out.close();
//    test();

    return 0;
}