#include <bits/stdc++.h>

using namespace std;

const int INF = 1e9;

class Treap {
    struct Node {
        int key, prior;
        int minV, maxV;
        int size;
        Node *l, *r;

        Node(int key): key(key), prior(rand()), minV(key), maxV(key), size(1), l(NULL), r(NULL) {}
        ~Node() { delete l; delete r; }
    };

    inline int size(Node *x) { return x ? x->size : 0; }
    inline int minV(Node *x) { return x ? x->minV : INF; }
    inline int maxV(Node *x) { return x ? x->maxV : 0; }

    inline void update(Node *x) {
        if (x) {
            x->size = size(x->l) + size(x->r) + 1;
            x->minV = min(x->key, min(minV(x->l), minV(x->r)));
            x->maxV = max(x->key, max(maxV(x->l), maxV(x->r)));
        }
    }

    Node* join(Node *l, Node *r) {
        if (!l || !r) return l ? l : r;
        if (l->prior < r->prior)
            return l->r = join(l->r, r), update(l), l;
        else 
            return r->l = join(l, r->l), update(r), r;
    }

    void splitByKey(Node *v, int x, Node* &l, Node* &r) {
        if (!v)
            l = r = NULL;
        else if (v->key < x)
            splitByKey(v->r, x, v->r, r), l = v;
        else
            splitByKey(v->l, x, l, v->l), r = v;
        update(v);
    }

    void splitByIndex(Node *v, int x, Node* &l, Node* &r) {
        if (!v) return void(l = r = NULL);
        int index = size(v->l) + 1;
        if (index < x)
            splitByIndex(v->r, x - size(v->l) - 1, v->r, r), l = v;
        else
            splitByIndex(v->l, x, l, v->l), r = v;
        update(v);
    }

    int valueAt(int pos, Node *x) {
        int index = size(x->l) + 1;
        if (pos == index) return x->key;
        if (pos < index) return valueAt(pos, x->l);
        return valueAt(pos - index, x->r);
    }

    bool find(int x, Node *v) {
        if (!v) return false;
        if (v->key == x) return true;
        if (v->key > x) return find(x, v->l);
        return find(x, v->r);
    }

    void show(Node *x) {
        if (!x) return;
        show(x->l);
        cerr << x->key << ' ';
        show(x->r);
    }

    Node *root;
    Node *l, *m, *r;
public:
    Treap() { root = NULL; }
    ~Treap() { delete root; }
    int size() { return size(root); }

    int insert(int x) {
        splitByKey(root, x, l, m);
        splitByKey(m, x + 1, m, r);
        int ans = 0;
        if (!m) m = new Node(x), ans = size(l) + 1;
        root = join(join(l, m), r);
        return ans;
    }

    int erase(int x) {
        splitByKey(root, x, l, m);
        splitByKey(m, x + 1, m, r);
        int ans = 0;
        if (m) {
            ans = size(l) + 1;
            delete m;
        }
        root = join(l, r);
        return ans;
    }

    void insertAt(int pos, int x) {
        splitByIndex(root, pos, l, r);
        root = join(join(l, new Node(x)), r);
    }

    void eraseAt(int x) {
        splitByIndex(root, x, l, m);
        splitByIndex(m, 2, m, r);
        delete m;
        root = join(l, r);
    }

    void updateAt(int pos, int newValue) {
        eraseAt(pos);
        insertAt(pos, newValue);
    }

    int valueAt(int pos) {
        assert(pos <= size());
        return valueAt(pos, root);
    }

    bool find(int x) {
        return find(x, root);
    }

    pair<int, int> getMaxMin(int i, int j) {
        splitByIndex(root, i, l, m);
        splitByIndex(m, j + 1, m, r);
        pair<int, int> ans = make_pair(m->maxV, m->minV);
        root = join(join(l, m), r);
        return ans;
    }

    void show() {
        cerr << "Size = " << size() << " ";
        cerr << "[";
        show(root);
        cerr << "]\n";
    }
};

void testTreap() {
    srand(time(0));
    Treap S;
    for (int i = 0; i < 10; ++i) {
        int pos = rand() % (S.size() + 1) + 1;
        int v = rand() % 10;
        cerr << "insertAt " << pos << ' ' << v << endl;
        S.insertAt(pos, v);
        S.show();
    }
    cerr << endl;
    for (int i = 0; i < 10; ++i) {
        int pos = rand() % (S.size()) + 1;
        cerr << "eraseAt " << pos << endl;
        S.eraseAt(pos);
        S.show();
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(NULL);
    freopen("zeap.in", "r", stdin);
    freopen("zeap.out", "w", stdout);
    //testTreap();
    Treap S, D;
    char cmd;
    while (cin >> cmd) {
        if (cmd == 'I') {
            int x; cin >> x;
            int index = S.insert(x);
            if (index != 0 && S.size() > 1) {
                if (index == S.size()) {
                    D.insertAt(index - 1, x - S.valueAt(index - 1));
                } else {
                    if (index > 1) D.updateAt(index - 1, x - S.valueAt(index - 1));
                    D.insertAt(index, S.valueAt(index + 1) - x);
                }
            }
        } else if (cmd == 'S') {
            int x; cin >> x;
            int index = S.erase(x);
            if (index == 0) {
                cout << -1 << '\n';
            }
            if (index != 0 && S.size() > 0) {
                if (index > S.size()) {
                    D.eraseAt(D.size());
                } else {
                    D.eraseAt(index);
                    if (index > 1) D.updateAt(index - 1, S.valueAt(index) - S.valueAt(index - 1));
                }
            }
        } else if (cmd == 'C') {
            int x; cin >> x;
            cout << (S.find(x) ? 1 : 0) << '\n';
        } else {
            cin >> cmd; cin >> cmd;
            int i = 1, j = S.size();
            int ans = -1;
            if (i < j) {
                if (cmd == 'N') {
                    ans = D.getMaxMin(i, j - 1).second;
                } else {
                    pair<int, int> maxMin = S.getMaxMin(i, j);
                    ans = maxMin.first - maxMin.second;
                }
            }
            cout << ans << '\n';
        }
        //S.show(); D.show(); cerr << endl;
        //assert(D.size() + 1 == S.size());
        //for (int i = 1; i < S.size(); ++i) assert(D.valueAt(i) == S.valueAt(i + 1) - S.valueAt(i));
    }
    return 0;
}