#include <vector>
#include <iostream>
using namespace std;

struct Heap
{
    vector<int> v, heap_v, pos;  ///v - значения, heap_v - куча индексов, pos - позиции в куче
    int n = 0;
    bool flag_; ///определитель кучи на максимум или минимум

    Heap(bool flag){
        heap_v.resize(1);
        flag_ = flag;
    }

    void siftUp(int i)
    {
        while ((i > 1) && ( v[heap_v[i/2]] > v[heap_v[i]])^flag_) {

            pos[heap_v[i]]  = i/2;
            pos[heap_v[i/2]] = i;
            swap(heap_v[i], heap_v[i/2]);
            i /= 2;
        }
    }

    void siftDown(int i) {
        while (2*i<=n){
            int l = 2*i;
            if ((l+1<=n) && (v[heap_v[l]] < v[heap_v[l+1]])^flag_) l++;
            if ((v[heap_v[l]] < v[heap_v[i]])^flag_ && l > n) break;
            else {
                pos[heap_v[l]]  = i;
                pos[heap_v[i]] = l;
                swap(heap_v[l], heap_v[i]);
                i = l;
            }
        }
    }

    void Insert(int new_el) {
        v.push_back(new_el);
        pos.push_back(n+1);
        heap_v.push_back(v.size()-1);
        n++;
        siftUp(n);
    }

    void Del(int i) {
        ///i = pos[i];
        swap(heap_v[i], heap_v[n]);

        heap_v.pop_back();
        n--;
        if(i <= n) {
            pos[heap_v[i]] = i;
            siftUp(i);
            siftDown(i);
        }
    }

    int Get(int i) { return v[heap_v[i]];}
};

int main()
{
    ios_base:: sync_with_stdio(false);
    cin.tie(0);
    int k;
    int x;
    string command, num;
    Heap min_heap(0);
    Heap max_heap(1);
    cin >> k;

    for (int i=0; i<k; i++){
        num="";
        cin >> command;

        for (int j=0; j<command.size(); j++){
            if ( '0' <= command[j] && command[j] <= '9') {num+= command[j];}
            else continue;
        }
        if (num != "") x = stoi(num);
        if (command[0]=='I') {
            min_heap.Insert(x);
            max_heap.Insert(x);
        }
        else {
            if (command[4] == 'i') {
                max_heap.Del(max_heap.pos[min_heap.heap_v[1]]);
                cout << min_heap.Get(1) << '\n';
                min_heap.Del(1);
            }

            else {
                min_heap.Del(min_heap.pos[max_heap.heap_v[1]]);
                cout << max_heap.Get(1) << '\n';
                max_heap.Del(1);
            }

        }
    }
}