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

int main() {
    int n;
    cin >> n;

    multiset<int> s;

    for (int i = 0; i < n; ++i) {
        int op;
        cin >> op;

        if (op == 1) {
            int x;
            cin >> x;
            s.insert(x);
        } else if (op == 2) {
            cout << *s.begin() << '\n';
        } else if (op == 3) {
            cout << *s.rbegin() << '\n';
        } else if (op == 4) {
            if (!s.empty()) {
                s.erase(s.begin());
            }
        } else if (op == 5) {
            if (!s.empty()) {
                auto it = s.end();
                --it;
                s.erase(it);
            }
        }
    }

    return 0;
}