T493686

#include <iostream>
#include <queue>
#include <vector>
#include <functional>
#include <map>

class ReversiblePriorityQueue {
    std::priority_queue<int> maxHeap; // 最大堆
    std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap; // 最小堆
    bool reversed = false; // 逆转标记
    std::map<int, int> counts; // 用于记录元素的存在性

public:
    void insert(int value) {
        maxHeap.push(value);
        minHeap.push(value);
        counts[value]++;
    }

    int deleteMax() {
        if (reversed) {
            return deleteMinInternal();
        } else {
            return deleteMaxInternal();
        }
    }

    int deleteMin() {
        if (reversed) {
            return deleteMaxInternal();
        } else {
            return deleteMinInternal();
        }
    }

    void reverse() {
        reversed = !reversed; // 切换逆转标记
    }

    int accessMin() {
        while (!minHeap.empty() && counts[minHeap.top()] == 0) {
            minHeap.pop();
        }
        return minHeap.top();
    }

    int accessMax() {
        while (!maxHeap.empty() && counts[maxHeap.top()] == 0) {
            maxHeap.pop();
        }
        return maxHeap.top();
    }

    // 公共方法检查是否已经逆转
    bool isReversed() {
        return reversed;
    }

private:
    int deleteMaxInternal() {
        while (!maxHeap.empty() && counts[maxHeap.top()] == 0) {
            maxHeap.pop();
        }
        int val = maxHeap.top();
        maxHeap.pop();
        counts[val]--;
        return val;
    }

    int deleteMinInternal() {
        while (!minHeap.empty() && counts[minHeap.top()] == 0) {
            minHeap.pop();
        }
        int val = minHeap.top();
        minHeap.pop();
        counts[val]--;
        return val;
    }
};

int main() {
    ReversiblePriorityQueue rpq;
    std::string command;
    int number;

    while (std::cin >> command) {
        if (command == "Insert") {
            std::cin >> number;
            rpq.insert(number);
        } else if (command == "DeleteMax") {
            std::cout << rpq.deleteMax() << std::endl;
        } else if (command == "DeleteMin") {
            std::cout << rpq.deleteMin() << std::endl;
        } else if (command == "Reverse") {
            rpq.reverse();
        } else if (command == "Access") {
            std::cin >> number;
            std::cout << (rpq.isReversed() ? rpq.accessMax() : rpq.accessMin()) << std::endl;
        }
    }

    return 0;
}