#include <cstdio>
#include <cmath>
#include "optimization.h"

using namespace std;

struct HEAP {
    int n;
    int h[100001];

    int min() {
        if (n) return h[1];
        else return 2147483647;
    }

    int down(int x) {
        while (true) {
            int l = 2 * x;
            if (l < n and h[l + 1] < h[l]) l++;
            if (l > n or h[l] >= h[x]) break;
            swap(h[l], h[x]), x = l;
        }
        return x;
    }

    void add(int x) {
        n++;
        h[n] = x;
        for (int i = n; (i > 1) and (h[i / 2] > h[i]); i /= 2)
            swap(h[i], h[i / 2]);
    }

    int pop() {
        swap(h[1], h[n]);
        n--;
        down(1);
        return h[n + 1];
    }

};

int main() {
#ifdef DEBUG
    assert(freopen("test.txt", "r", stdin));
#endif

    HEAP minimum, min_del;
    HEAP maximum, max_del;

    int n = readInt();

    while (n != 0) {
        char s[99];
        readWord(s);
        if (s[0] == 'I') {
            int x = atoi(s + 7);
            minimum.add(x);
            maximum.add(-x);
        } else if (s[4] == 'i') {
            while (min_del.min() == minimum.min()) {
                minimum.pop();
                min_del.pop();
            }
            int x = minimum.pop();
            writeInt(x);
            writeChar('\n');
            max_del.add(-x);
        } else if (s[4] == 'a') {
            while (max_del.min() == maximum.min()) {
                maximum.pop();
                max_del.pop();
            }
            int x = -maximum.pop();
            writeInt(x);
            writeChar('\n');
            min_del.add(x);
        }
        n--;
    }
}