#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;

namespace SHAWN {
    const int N = 1e5 + 7;
    priority_queue<int, vector<int>, greater<int> > frt;
    priority_queue<int, vector<int>, less<int> > bke;
    int a[N];
    int n, m;
    signed work()
    {
        cin >> n;
        for (int i = 1; i <= n; ++i) { cin >> a[i]; }
        sort(a + 1, a + n + 1);
        int mid = (n + 1) / 2;
        for (int i = 1; i <= mid; ++i) { bke.emplace(a[i]); }
        for (int i = mid + 1; i <= n; ++i) { frt.emplace(a[i]); }
        cin >> m;
        while (m--) {
            string opt; cin >> opt;
            if (opt == "add") {
                int num; cin >> num;
                if (num > frt.top()) { frt.emplace(num); }
                else if (num < bke.top()) { bke.emplace(num); }
                while (frt.size() > bke.size()) {
                    bke.emplace(frt.top());
                    frt.pop();
                }
                while (bke.size() > frt.size() + 1) {
                    frt.emplace(bke.top());
                    bke.pop();
                }
            }
            else if (opt == "mid") { cout << bke.top() << '\n'; }
        }
        return 0;
    }
}

signed main() {
    ios :: sync_with_stdio(false);
    cin.tie(nullptr);
    return SHAWN :: work();
}