//ALEX ENACHE

#include <vector>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include <unordered_map>
#include <time.h>
#include <iomanip>
#include <deque>
#include <math.h>
#include <cmath>
#include <assert.h>
#include <stack>
#include <bitset>
#include <random>
#include <chrono>

using namespace std;

//#include <iostream>

#include <fstream>
ifstream cin ("zeap.in");ofstream cout ("zeap.out");

struct nod {
    int key , priority , MIN , MAX , MIN_DIF;
    nod *left , *right;
    nod (int key , int priority , nod *left , nod *right , int MIN , int MAX , int MIN_DIF){
        this -> key = key;
        this -> priority = priority;
        this -> left = left;
        this -> right = right;
        this -> MIN = MIN;
        this -> MAX = MAX;
        this -> MIN_DIF = MIN_DIF;
    }
};

nod *nil , *root;

const int limit = 1e9 + 1;

void init(){
    nil = new nod(0 , 0 , NULL , NULL , limit , 0 , limit);
    root = nil;
}

void recalc(nod *&now){
    now -> MIN = min(now -> left -> MIN , now -> key);
    now -> MAX = max(now -> right -> MAX , now -> key);
    int st = limit , dr = limit;
    if (now -> left != nil){
        st = now -> key - now -> left -> MAX;
    }
    if (now -> right != nil){
        dr = now -> right -> MIN - now -> key;
    }
    now -> MIN_DIF = min ( min ( now -> left -> MIN_DIF , now -> right -> MIN_DIF ) , min ( st , dr ) );
}

void rotleft(nod *&now){
    nod *aux = now -> left;
    now -> left = aux -> right;
    aux -> right = now;

    //recalculez MIN , MAX , MIN_DIF pt now si aux
    recalc(now);
    recalc(aux);

    now = aux;
}

void rotright(nod *&now){
    nod *aux = now -> right;
    now -> right = aux -> left;
    aux -> left = now;

    //recalculez MIN , MAX , MIN_DIF pt now si aux
    recalc(now);
    recalc(aux);

    now = aux;
}

void balance(nod *&now){
    if (now -> priority < now -> left -> priority){
        rotleft(now);
    }
    if (now -> priority < now -> right -> priority){
        rotright(now);
    }
    recalc(now);
}

void insert(nod *&now , int key , int priority){
    if (now == nil){
        now = new nod(key , priority , nil , nil , key , key , limit);
        return;
    }
    if (now -> key == key){
        return;
    }

    if (key < now -> key){
        insert(now -> left , key , priority);
    }
    else{
        insert(now -> right , key , priority);
    }

    balance(now);
}

void erase(nod *&now , int key){
    if (now == nil){
        cout<<-1<<'\n';
        return;
    }

    if (key < now -> key){
        erase(now -> left , key);
        recalc(now);
    }
    else if (key > now -> key){
        erase(now -> right , key);
        recalc(now);
    }
    else{
        if (now -> left == nil && now -> right == nil){
            delete now;
            now = nil;
            return;
        }
        if (now -> left -> priority > now -> right -> priority){
            rotleft(now);
        }
        else{
            rotright(now);
        }
        erase(now , key);
    }
}

void search(nod *&now , int key){
    if (now == nil){
        cout<<0<<'\n';
        return;
    }
    if (now -> key == key){
        cout<<1<<'\n';
        return;
    }
    if (key < now -> key){
        search(now -> left , key);
    }
    else{
        search(now -> right , key);
    }
}

void verif(nod *now){
    if (now == nil){
        return;
    }
    verif(now -> left);
    cout<<now->key<<" "<<now->MIN<<" "<<now->MAX<<" "<<now->MIN_DIF<<'\n';
    verif(now -> right);
}

int main() {

    //freopen("input", "r", stdin);freopen("output", "w", stdout);

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    srand(time(NULL));
    init();

    string s;
    int x;

    while (cin>>s){
        if (s == "I"){
            cin>>x;
            insert(root , x , rand() + 1);
        }
        if (s == "S"){
            cin>>x;
            erase(root , x);
        }
        if (s == "C"){
            cin>>x;
            search(root , x);
        }
        if (s == "MAX"){
            if (root -> MAX - root -> MIN <= 0){
                cout<<-1<<'\n';
            }
            else{
                cout<<root -> MAX - root -> MIN<<'\n';
            }
        }
        if (s == "MIN"){
            if (root -> MIN_DIF == limit){
                cout<<-1<<'\n';
            }
            else{
                cout<<root -> MIN_DIF<<'\n';
            }
        }
    }

    //verif(root);

    return 0;
}