#include <iostream>
#include <string>

template <typename T>
class Deque {
 private:
    int head, tail;
    int capacity;
    T *deque;
    int s;

    bool isFull() {
        return (head == 0 && tail == capacity - 1) || (head == tail + 1);
    }

    void expand() {
        T *buffer = new T[capacity];
        int index = 0;
        while (!empty()) {
            buffer[index++] = pop_front();
        }
        delete[] deque;
        deque = new T[capacity * 2];
        capacity *= 2;
        for (size_t i = 0; i < index; i++) {
            push_back(buffer[i]);
        }
    }

 public:
    Deque() {
        capacity = 10;
        head = -1;
        tail = 0;
        deque = new T[capacity];
        s = 0;
    }

    void push_front(T x) {
        if (isFull()) {
            expand();
        }
        s++;
        if (head == -1) {
            head = 0;
            tail = 0;
        } else if (head == 0) {
            head = capacity - 1;
        } else {
            head--;
        }
        deque[head] = x;
    }

    void push_back(T x) {
        if (isFull()) {
            expand();
        }
        s++;
        if (head == -1) {
            head = 0;
            tail = 0;
        } else if (tail == capacity - 1) {
            tail = 0;
        } else {
            tail++;
        }

        deque[tail] = x;
    }

    bool empty() {
        return head == -1;
    }

    T pop_front() {
        s--;
        if (head == tail) {
            int result = deque[head];
            head = -1;
            tail = -1;
            return result;
        } else {
            if (head == capacity - 1) {
                T result = deque[head];
                head = 0;
                return result;
            } else {
                T result = deque[head];
                head++;
                return result;
            }
        }
    }

    T pop_back() {
        s--;
        if (head == tail) {
            T result = deque[head];
            head = -1;
            tail = -1;
            return result;
        } else if (tail == 0) {
            tail = capacity - 1;
            return deque[0];
        } else {
            T result = deque[tail];
            tail--;
            return result;
        }
    }

    T front() {
        return deque[head];
    }

    T back() {
        return deque[tail];
    }

    int size() {
        return s;
    }

    void clear() {
        delete[] deque;
        tail = 0;
        head = -1;
        s = 0;
        capacity = 10;
        deque = new T[capacity];
    }
};

void insertBack(Deque<int> *deque1, Deque<int> *deque2) {
    int num;
    std::cin >> num;

    deque2->push_back(num);
    if (deque2->size() > deque1->size()) {
        deque1->push_back(deque2->pop_front());
    }
}

void insertMiddle(Deque<int> *deque1, Deque<int> *deque2) {
    int num;
    std::cin >> num;

    if (deque1->size() == deque2->size()) {
        deque1->push_back(num);
    } else {
        deque2->push_front(num);
    }
}

void remove(Deque<int> *deque1, Deque<int> *deque2) {
    std::cout << deque1->pop_front() << "\n";
    if (deque2->size() > deque1->size()) {
        deque1->push_back(deque2->pop_front());
    }
}

void handle(char command, Deque<int> *deque1, Deque<int> *deque2) {
    switch (command) {
        case '+':
            insertBack(deque1, deque2);
            return;
        case '*':
            insertMiddle(deque1, deque2);
            return;
        case '-':
            remove(deque1, deque2);
            return;
        default:
            return;
    }
}


int main() {
    // делим всех жителей в пробке на две группы.
    // в первом деке всегда будет >= жителей чем во втором.
    Deque<int> deque1;
    Deque<int> deque2;
    int n;
    std::cin >> n;
    char command;

    for (int i = 0; i < n; i++) {
        std::cin >> command;
        handle(command, &deque1, &deque2);
    }

    return 0;
}