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) 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;
}