#include <bits/stdc++.h>

using namespace std;

struct Treap{
    Treap *st, *dr;
    int key, pri, mn, mx, mndif;
    Treap(Treap *leftson, Treap *rightson, int val, int prior, int mini, int maxi, int minimdif){
        this->st = leftson;
        this->dr = rightson;
        key = val;
        pri = prior;
        mn = mini;
        mx = maxi;
        mndif = minimdif;
    }
} *root, *NILL;

bool findElem(Treap *&node, int val){
    if(node == NILL) return 0;
    if(node->key == val) return 1;
    if(node->key > val) return findElem(node->st, val);
    return findElem(node->dr, val);
}

int getMaxDif(Treap *&node){
    if(node->mx > node->mn) return node->mx - node->mn;
    return -1;
}

int getMinDif(Treap *&node){
    if(node->mndif> 0 && node->mndif < 1e9) return node->mndif;
    return -1;
}

void recalc(Treap *&node){
    if(node == NILL) return;
    node->mx = node->mn = node->key;
    node->mndif = 1e9;
    if(node->st != NILL){
        node->mx = max(node->mx, node->st->mx);
        node->mn = min(node->mn, node->st->mn);
        node->mndif = min(node->mndif, min(node->st->mndif, node->key - node->st->mx));
    }
    if(node->dr != NILL){
        node->mx = max(node->mx, node->dr->mx);
        node->mn = min(node->mn, node->dr->mn);
        node->mndif = min(node->mndif, min(node->dr->mndif, node->dr->mn - node->key));
    }
}

void leftRotate(Treap *&node){
    recalc(node);
    Treap *aux = node->st;
    node->st = aux->dr;
    aux->dr = node;
    node = aux;
    recalc(node->st);
    recalc(node->dr);
    recalc(node);
}

void rightRotate(Treap *&node){
    recalc(node);
    Treap *aux = node->dr;
    node->dr = aux->st;
    aux->st = node;
    node = aux;
    recalc(node->st);
    recalc(node->dr);
    recalc(node);
}

void balance(Treap *&node){
    if(node == NILL) return;
    recalc(node);
    if(node->st != NILL && node->st->pri > node->pri) leftRotate(node);
    if(node->dr != NILL && node->dr->pri > node->pri) rightRotate(node);
}

void grow(Treap *&node, int val, int prior){
    if(node == NILL){
        node = new Treap(NILL, NILL, val, prior, val, val, 1e9);
        return;
    }
    if(node->key > val) grow(node->st, val, prior);
    else grow(node->dr, val, prior);
    balance(node);
}

void cut(Treap *&node, int val){
    if(node->key > val) cut(node->st, val);
    else if(node->key < val) cut(node->dr, val);
    else{
        if(node->st == NILL && node->dr == NILL){
            delete node;
            node = NILL;
        }
        else if(node->st != NILL && node->dr != NILL){
            if(node->st->pri > node->dr->pri) leftRotate(node);
            else rightRotate(node);
            cut(node, val);
        }
        else{
            if(node->st != NILL) leftRotate(node);
            else rightRotate(node);
            cut(node, val);
        }
    }
    balance(node);
}

void dfs(Treap *&node){
    if(node == NILL) return;
    cout << node->key << " " << node->pri << "\n";
    dfs(node->st);
    dfs(node->dr);
}

int main()
{
    ifstream fin ("zeap.in");
    ofstream fout ("zeap.out");
    srand(time(NULL));
    NILL = new Treap(NULL, NULL, 0, 0, 0, 0, 0);
    root = NILL;
    char c;
    int x;
    while(c != EOF){
        c = fin.get();
        if(c == 'I'){
            fin >> x;
            if(!findElem(root, x))
                grow(root, x, rand()%666013 + 1);
        }
        if(c == 'S'){
            fin >> x;
            if(findElem(root, x))
                cut(root, x);
            else fout << "-1\n";
        }
        if(c == 'C'){
            fin >> x;
            fout << findElem(root, x) << "\n";
        }
        if(c == 'M'){
            c = fin.get();
            if(c == 'A')
                fout << getMaxDif(root) << "\n";
            else
                fout << getMinDif(root) << "\n";
            fin.get();
        }
        fin.get();
    }
    return 0;
}