#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <utility>
#include <string>

using namespace std;

const int inf = 1e9 + 5;

struct treap {
    int key, pr;

    int minimum, maximum;
    int dif_min;

    treap *left, *right;

    treap(int _key = 0, int _pr = 0, int _minimum = 0, int _maximum = 0, int _dif_min = 0, treap *_left = NULL, treap *_right = NULL):
            key(_key), pr(_pr), minimum(_minimum), maximum(_maximum), dif_min(_dif_min), left(_left), right(_right) {}
} *root, *nil;

inline void calc_dp(treap *t) {
    if (t != nil) {
        t -> minimum = min(t -> key, min(t -> left -> minimum, t -> right -> minimum));
        t -> maximum = max(t -> key, max(t -> left -> maximum, t -> right -> maximum));
        t -> dif_min = min(min(t -> left -> dif_min, t -> right -> dif_min), max(t -> key, t -> right -> minimum) - min(t -> key, t -> left -> maximum));
    }
}

void dfs(treap *t, string aux = "") {
    if (t == nil)
        return ;

    dfs(t -> right, aux + " ");
    cout << aux << t -> key << '\n';
    dfs(t -> left, aux + " ");
}

inline void print(treap *t) {
    cout << "Treapul e:" << endl;
    dfs(t);
    cout << "#end" << endl << endl;
}

pair <treap*, treap*> split(treap *t, int key) {
    if (t == nil)
        return make_pair(nil, nil);

    pair <treap*, treap*> aux;
    if (key < t -> key) {
        aux = split(t -> left, key);

        t -> left = aux.second;
        aux.second = t;
    }
    else {
        aux = split(t -> right, key);

        t -> right = aux.first;
        aux.first = t;
    }

    calc_dp(t);
    return aux;
}

treap* join(treap *l, treap *r) {
    if (l == nil)
        return r;
    else if (r == nil)
        return l;

    if (l -> pr > r -> pr) {
        l -> right = join(l -> right, r);

        calc_dp(l);
        return l;
    }
    else {
        r -> left = join(l, r -> left);

        calc_dp(r);
        return r;
    }
}

treap* insert(treap *t, int key, int pr) {
    if (pr > t -> pr) {
        pair <treap*, treap*> aux = split(t, key);

        t = new treap(key, pr, key, key, 0, aux.first, aux.second);
        dfs(t);
    }
    else if (key == t -> key)
        return t;
    else if (key < t -> key)
        t -> left = insert(t -> left, key, pr);
    else
        t -> right = insert(t -> right, key, pr);

    calc_dp(t);
    return t;
}

bool find(treap *t, int key) {
    if (t == nil)
        return false;
    else if (key == t -> key)
        return true;
    else if (key < t -> key)
        return find(t -> left, key);
    else
        return find(t -> right, key);
}

treap* erase(treap *t, int key) {
    if (t == nil)
        return t;
    else if (key == t -> key) {
        treap *aux = t;
        t = join(t -> left, t -> right);

        delete aux;
    }
    else if (key < t -> key)
        t -> left = erase(t -> left, key);
    else if (key > t -> key)
        t -> right = erase(t -> right, key);
    calc_dp(t);

    return t;
}

inline void test_treap() {
    root = nil = new treap(-1, -1, inf, -inf, inf);
    nil -> left = nil -> right = nil;

    root = insert(root, 1, rand());
    root = insert(root, 2, rand());
    root = insert(root, 3, rand());
    root = insert(root, 4, rand());
    root = insert(root, 5, rand());

    root = erase(root, 4);
    root = erase(root, 3);

    print(root);
}

int main()
{
    srand(time(NULL));

    //test_treap();
    root = nil = new treap(-1, -1, inf, -inf, inf);
    nil -> left = nil -> right = nil;

    string op;
    int x;

    while (1) {
        cin >> op;

        if (op == "I") {
            cin >> x;
            root = insert(root, x, rand());
        }
        else if (op == "S") {
            cin >> x;

            if (!find(root, x))
                cout << "-1\n";
            else
                root = erase(root, x);
        }
        else if (op == "C") {
            cin >> x;
            cout << find(root, x) << '\n';
        }
        else if (op == "MAX")
            cout << root -> maximum - root -> minimum << '\n';
        else
            cout << root -> dif_min << '\n';
    }

    return 0;
}