#include <bits/stdc++.h>
#define MAX 131072
#define MOD 1000000007

using namespace std;

ifstream fin("zeap.in");
ofstream fout("zeap.out");

int xVal, ans, N;
int valMax, valMinAbs, valMin;
char sTip[5];

struct Treap{
    int priority, val;
    Treap *left, *right;
    Treap(int p, int x){
        left = right = NULL;
        priority = p;
        val = x;
    }
};

Treap *root = NULL;
Treap *tForDelete;

inline int good_rand() {
    return (rand() << 14) | rand();
}

inline Treap *tRotLeft(Treap *node){
    Treap *aux = node->right;
    node->right = aux->left;
    aux->left = node;
    return aux;
}

inline Treap *tRotRight(Treap *node){
    Treap *aux = node->left;
    node->left = aux->right;
    aux->right = node;
    return aux;
}

inline Treap *tBalance(Treap *node){
    if(node->left != NULL && node->left->priority > node->priority)
        return tRotRight(node);
    if(node->right != NULL && node->right->priority > node->priority)
        return tRotLeft(node);
    return node;
}

Treap *tInsert(Treap *node){
    if(node == NULL){
        N++;
        node = new Treap(good_rand(), xVal);
        return node;
    } else if(node->val == xVal)
        return node;
    if(node->val >= xVal)
        node->left = tInsert(node->left);
    else node->right = tInsert(node->right);
    return tBalance(node);
}

inline bool tSearch(Treap *node){
    if(node == NULL)
        return false;
    else if(node->val == xVal){
        tForDelete = node;
        return true;
    }
    if(node->val > xVal)
        return tSearch(node->left);
    else return tSearch(node->right);
}

inline void tMaxRight(Treap *node){
    valMax = max(valMax, node->val);
    if(node->left == NULL && node->right == NULL)
        return;
    if(node->right != NULL)
        tMaxRight(node->right);
    else tMaxRight(node->left);
}

inline void tMinLeft(Treap *node){
    if(node->val < valMinAbs){
        valMin = valMinAbs;
        valMinAbs = node->val;
    } else if(node->val < valMin)
        valMin = node->val;
    if(node->left == NULL && node->right == NULL)
        return;
    if(node->left != NULL)
        tMinLeft(node->left);
    else tMinLeft(node->right);
}

Treap *tDelete(Treap *node, bool flag){
    if(node->val == xVal || flag){
        if(node->left == NULL && node->right == NULL){
            ans = 0;
            delete node;
            return NULL;
        }
        Treap *aux;
        if(node->left == NULL){
            aux = tRotLeft(node);
            aux->left = tDelete(aux->left, 1);
        } else if(node->right == NULL){
            aux = tRotRight(node);
            aux->right = tDelete(aux->right, 1);
        } else if(node->left->priority > node->right->priority){
            aux = tRotLeft(node);
            aux->left = tDelete(aux->left, 1);
        } else {
            aux = tRotRight(node);
            aux->right = tDelete(aux->right, 1);
        }
        return tBalance(aux);
    } else {
        if(node->val > xVal && node->left != NULL)
            node->left = tDelete(node->left, 0);
        else if(node->right != NULL)
            node->right = tDelete(node->right, 0);
        return tBalance(node);
    }
}

int main(){

    srand(time(NULL));

    while(true){
        fin >> sTip;
        if(fin.eof()) break;
        if(sTip[0] != 'M'){
            fin >> xVal;
            if(sTip[0] == 'I')
                root = tInsert(root);
            else if(sTip[0] == 'S'){
                ans = -1;
                root = tDelete(root, 0);
                if(ans == -1)
                    fout << ans << '\n';
            } else if(sTip[0] == 'C')
                fout << tSearch(root) << '\n';
        } else {
            if(N < 2){
                fout << -1 << '\n';
                continue;
            }
            valMinAbs = valMin = 2e9; valMax = 0;
            tMinLeft(root);
            if(sTip[1] == 'A'){
                tMaxRight(root);
                fout << valMax - valMinAbs << '\n';
            } else fout << valMin - valMinAbs << '\n';
        }
    }

    return 0;
}