#include <iostream>
#include <deque>

using namespace std;

struct DoubleQueue {
    deque<int> first, second;

    void normalize() {
        int target_first_size = (first.size() + second.size() + 1) / 2;

        if (first.size() < target_first_size) {
            while (first.size() < second.size()) {
                first.push_back(second.front());
                second.pop_front();
            }
        } else {
            while (first.size() > target_first_size) {
                second.push_front(first.back());
                first.pop_back();
            }
        }
    }

    void push_back(int x) {
        second.push_back(x);
        normalize();
    }

    void push_middle(int x) {
        first.push_back(x);
        normalize();
    }

    int pop() {
        int result = first.front();
        first.pop_front();
        normalize();
        return result;
    }
};

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

    for (int i = 0; i < n; ++i) {
        string query;
        cin >> query;
        if (query == "+") {
            int x;
            cin >> x;
            q.push_back(x);
        } else if (query == "*") {
            int x;
            cin >> x;
            q.push_middle(x);
        } else {
            cout << q.pop() << "\n";
        }
    }

    return 0;
}