#include <bits/stdc++.h>

using namespace std;

FILE *input;
ofstream fout("zeap.out");

struct Node {
    int val;
    Node *parent, *left, *right;

    Node(int v = 0, Node *p = nullptr) {
        val = v;
        parent = p;
        left = right = nullptr;
    }
};

class cmp {
public:
    bool operator()(pair<int, int> &X, pair<int, int> &Y) {
        return abs(X.second - X.first) > abs(Y.second - Y.first);
    }
};

class Zeap {
public:
    Zeap() : m_root(nullptr), m_size(0), dif() {}

    Node *getRoot() {
        return m_root;
    }

    int getSize() {
        return m_size;
    }

    Node *&findNode(int x) {
        Node *current = m_root;
        Node *save = current;

        while (current) {
            save = current;

            if (x == current->val) {
                return current;
            } else if (x < current->val) {
                current = current->left;
            } else {
                current = current->right;
            }
        }

        return save;
    }

    bool find(int x) {
        Node *found = findNode(x);

        if (found) {
            return findNode(x)->val == x;
        }

        return false;
    }

    void visitNode(Node *node, int x) {
        if (node->val != x) {
            dif.push(make_pair(node->val, x));
        }

        cout << node->val << ' ';

        if (node->left) {
            visitNode(node->left, x);
        }

        if (node->right) {
            visitNode(node->right, x);
        }
    }

    void insert(int x) {
        Node *found = findNode(x);
        bool canInsert = found == nullptr;
        ++m_size;

        if (!canInsert) {
            if (found->val != x) {
                canInsert = true;
            }
        }

        if (canInsert) { // x nu se afla in arbore, found e parintele lui
            Node *newNode;

            if (found) {
                newNode = new Node(x, found);

                if (x < found->val) {
                    found->left = newNode;
                } else {
                    found->right = newNode;
                }
            } else {
                newNode = new Node(x);
                m_root = newNode;
            }

            visitNode(m_root, x);
            cout << '\n';
        }
    }

    Node *minimum(Node *start) {
        if (start->left) {
            do {
                start = start->left;
            }
            while (start->left);
        }

        return start;
    }

    Node *maximum(Node *start) {
        if (start->right) {
            do {
                start = start->right;
            }
            while (start->right);
        }

        return start;
    }

    Node *successor(Node *x) {
        if (x->right) {
            return minimum(x->right);
        }

        Node *y = x->parent;

        if (y) {
            while (y->right == x) {
                x = y;
                y = y->parent;

                if (y == nullptr) {
                    break;
                }
            }
        }

        return y;
    }

    Node *predecessor(Node *x) {
        if (x->left) {
            return maximum(x->left);
        }

        Node *y = x->parent;

        if (y) {
            while (y->left == x) {
                x = y;
                y = y->parent;

                if (y == nullptr) {
                    break;
                }
            }
        }

        return y;
    }

    int deleteNode(int x) {
        Node *found = findNode(x);

        if (!found) {
            return -1;
        }

        if (found->val != x) {
            return -1;
        } else if (!found->left && !found->right) {
            if (found->parent->val < found->val) {
                found->parent->right = nullptr;
            } else {
                found->parent->left = nullptr;
            }

            delete found;
        } else if (found->left && !found->right) {
            if (found->parent->val < found->val) {
                found->parent->right = found->left;
            } else {
                found->parent->left = found->left;
            }

            delete found;
        } else if (!found->left && found->right) {
            if (found->parent->val < found->val) {
                found->parent->right = found->right;
            } else {
                found->parent->left = found->right;
            }

            delete found;
        } else {
            Node *toDelete = successor(found);
            found->val = toDelete->val;

            delete toDelete;
        }

        --m_size;

        return 1;
    }

    int maxDif() {
        if (m_size < 2) {
            return -1;
        }

        return maximum(m_root)->val - minimum(m_root)->val;
    }

    int minDif() {
        pair<int, int> p = dif.top();

        while (!find(p.first) || !find(p.second)) {
            dif.pop();

            if (dif.empty()) {
                return -1;
            }

            p = dif.top();
        }

        return abs(p.second - p.first);
    }

private:
    Node *m_root;
    int m_size;
    priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> dif;
};

int strToNum(char *command) {
    int num = 0;

    for (int i = 2; command[i] != '\n'; ++i) {
        num = num * 10 + command[i] - '0';
    }

    return num;
}

int main() {
    input = fopen("zeap.in", "r");
    char command[13];
    Zeap tree;

    while (fgets(command, 13, input)) {
        if (command[0] == 'I') {
            tree.insert(strToNum(command));
        } else if (command[0] == 'C') {
            fout << tree.find(strToNum(command)) << '\n';
        } else if (command[0] == 'S') {
            int res = tree.deleteNode(strToNum(command));

            if (res == -1) {
                fout << tree.deleteNode(strToNum(command)) << '\n';
            }
        } else if (!strcmp(command, "MAX\n")) {
            fout << tree.maxDif() << '\n';
        } else {
            fout << tree.minDif() << '\n';
        }
    }

    fout.close();

    return 0;
}