#include <algorithm>
#include <bitset>
#include <chrono>
#include <cmath>
#include <deque>
#include <fstream>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <vector>

template <typename T1, typename T2> inline bool chkmin(T1 &x, const T2 &y) {
    if (x > y) {
        x = y;
        return 1;
    }
    return 0;
}
template <typename T1, typename T2> inline bool chkmax(T1 &x, const T2 &y) {
    if (x < y) {
        x = y;
        return 1;
    }
    return 0;
}

using namespace std;

const int maxn = 2e5 + 20;

ostream &operator<<(ostream &out, const pair<int, int> &v) {
    out << v.first << ", " << v.second;
    return out;
}

template <typename T> ostream &operator<<(ostream &out, const vector<T> &v) {
    for (auto &x : v)
        out << x << " ";
    return out;
}

istream &operator>>(istream &in, pair<int, int> &a) {
    in >> a.first >> a.second;
    return in;
}

const long long inf = (long long)2e9;
const long double pi = asin(1) * 2;
const long double eps = 1e-8;
const long long mod = (long long)1e9 + 7;
const long long ns = 97;

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

struct tree {
    vector<int> t;
    int size = 0, capacity;

    tree(int n) {
        while ((1 << size) < n)
            ++size;
        ++size;
        size = (1 << size);
        capacity = (size >> 1);
        t = vector<int>(size);
    }

    int get(int cur, int k) {
        if (cur * 2 >= size)
            return cur - capacity;
        if (t[cur * 2] >= k)
            return get(cur * 2, k);
        return get(cur * 2 + 1, k - t[cur * 2]);
    }

    void add(int i, int x) {
        i += capacity;
        t[i] += x;
        i >>= 1;
        while (i) {
            t[i] = t[i * 2] + t[i * 2 + 1];
            i >>= 1;
        }
    }
};

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n;
    cin >> n;
    vector<pair<int, int>> kek;
    for (int i = 0; i < n; ++i) {
        string t;
        int x = 0;
        cin >> t;
        if (t == "add") {
            cin >> x;
            kek.push_back({0, x});
        }
        if (t == "min")
            kek.push_back({1, x});
        if (t == "max")
            kek.push_back({2, x});
        if (t == "mid")
            kek.push_back({3, x});
    }
    vector<int> tmp;
    for (auto &x : kek)
        tmp.push_back(x.second);
    sort(tmp.begin(), tmp.end());
    tmp.resize(unique(tmp.begin(), tmp.end()) - tmp.begin());
    for (auto &x : kek)
        x.second =
            (int)(lower_bound(tmp.begin(), tmp.end(), x.second) - tmp.begin());
    int m = (int)tmp.size();
    tree goo(m);
    int cnt = 0;
    for (auto &t : kek) {
        if (t.first == 0) {
            goo.add(t.second, 1);
            ++cnt;
        } else if (t.first == 1) {
            int x = goo.get(1, 1);
            cout << tmp[x] << '\n';
            goo.add(x, -1);
            --cnt;
        } else if (t.first == 2) {
            int x = goo.get(1, cnt);
            cout << tmp[x] << '\n';
            goo.add(x, -1);
            --cnt;
        } else {
            int x = goo.get(1, (cnt + 1) / 2);
            cout << tmp[x] << '\n';
            goo.add(x, -1);
            --cnt;
        }
    }
}