using namespace std;
#include<iostream>
#include<fstream>
#include<cstdlib>
#include<ctime>
#define oo 0x3f3f3f3f
ofstream fout("zeap.out");
struct T{
int key,p,min,max,difmin;
T *l,*r;
T(){}
T(int key,int p,int min, int max,int difmin, T* l,T* r)
{
    this->key=key;
    this->p=p;
    this->min=min;
    this->max=max;
    this->difmin=difmin;
    this->l=l;
    this->r=r;


}
};
T *R,*nil;

void init()
{
    R=nil=new T(-oo,-oo,oo,-oo,oo,NULL,NULL);

}

void rotleft(T* n)
{

    T* t=n->l;
    n->l=t->r;
    t->r=n;
    n=t;
}

void rotright(T* n)
{

    T* t=n->r;
    n->r=t->l;
    t->l=n;
    n=t;

}

void update(T* n)
{
    if(n!=nil)
    {
        n->min=min(min(n->l->min,n->r->min),n->key);
        n->max=max(max(n->l->max,n->r->max),n->key);
        n->difmin=min(min(n->l->difmin,n->r->difmin),min(n->key - n->l->max, n->r->min - n->key));

    }

}


void balance(T* n)
{

    if(n->l->p > n->p) rotleft(n), update(n->r), update(n);
    if(n->r->p > n->p) rotright(n), update(n->l), update(n);



}

void insert(T* n,int key)
{
    if(n==nil) {n=new T(key,rand(),key,key,oo,nil,nil); return;}

    if(key==n->key) return;

    if(key<n->key) insert(n->l,key);
    if(key>n->key) insert(n->r,key);

    update(n);
    balance(n);

}

void cauta(T* n,int key)
{
    if(n==nil) {fout<<"0\n"; return;}

    if(key==n->key) {fout<<"1\n"; return;}
    if(key<n->key) cauta(n->l,key);
    if(key>n->key) cauta(n->r,key);

}

void erase(T* n,int key)
{
    if(n==nil) {fout<<"-1\n"; return;}

    if(key<n->key) erase(n->l,key);
    if(key>n->key) erase(n->r,key);

    if(key==n->key)
    {
        if(n->l==nil && n->r==nil)
        {
            delete n;
            n=nil;
            return;
        }

        else
        {
            if(n->l->p > n->r->p)
            {
                rotleft(n);

                update(n->r);
                update(n);
            }
            else
            {
                rotright(n);

                update(n->l);
                update(n);

            }
            erase(n,key);
        }
    }

    update(n);
}
void cit()
{
    char c;
    int x;
    int y=0;
    ifstream fin("zeap.in");
    while(fin>>c)
    {

        if(c=='I') {fin>>x; insert(R,x);}
        if(c=='S') {fin>>x; erase(R,x);}
        if(c=='C') {fin>>x; cauta(R,x);}
        if(c=='M') {
        fin>>c;fin>>c;
        if(R==nil ||(R->l==nil && R->r==nil))
           fout<<-1<<"\n";
          else
           if(c=='X')
              fout<<R->max - R->min<<"\n";
            else
              fout<<R->difmin<<"\n";

        }


    }
    fin.close();
}

int main()
{   srand(time(0));
    init();
    cit();
    fout.close();
    return 0;
}