using namespace std;

#include<iostream>
#include<fstream>
#include<cmath>
ofstream fout("zeap.out");
#define oo 0x3f3f3f3f
struct nod{
    int p;
    int min,max;
    int difmin;
    int h;
    int v;
    nod *r,*l;
};
typedef nod* treap;
treap R,nil;
void init()
{
    nil=new nod;
    nil->r=nil->l=NULL;
    nil->h=0;
    nil->difmin=nil->min=oo;
    nil->max=-oo;
    nil->p=-oo;
    R=nil;

}
void update(treap &n)
{   n->min=min(n->l->min,n->v);
    n->max=max(n->r->max,n->v);
    n->difmin=min(min(n->l->difmin,n->r->difmin),min(abs(n->v-n->l->max),abs(n->r->min-n->v)));
}
void  rotleft(treap &n)
{treap t=n->l;
n->l=t->r;t->r=n;
update(n),update(t);
n=t;
}
void rotright(treap &n)
{treap t=n->r;
n->r=t->l; t->l=n;
update(n),update(t);
n=t;
}
void balance(treap&n)
{if(n->l->p>n->p)
  rotleft(n);
  else   
 if(n->r->p>n->p)
  rotright(n);
  update(n);
}
void insereaza(treap &n,int val)
{
    if(n==nil)
    {n=new nod;
    n->r=nil;
    n->l=nil;
    n->difmin=oo;
    n->h=1;
    n->p=rand();
    n->min=n->max=n->v=val;
    return;
    }
    if(val>n->v)
        insereaza(n->r,val);
    if(val<n->v)
        insereaza(n->l,val);
    update(n);
    balance(n);
    update(n);
}
void sterge(treap& n,int val)
{
    if(n==nil) {fout<<"-1"<<"\n";return ;}
    if(n->v>val)
        sterge(n->l,val);
       else {if(val>n->v) sterge(n->r,val);
        else
         {if(n->l==nil&&n->r==nil)
           {
            delete n; n=nil;

           }

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


          sterge(n,val) ;
         }

        }
       }
       if(n!=nil)
   update(n);
}

void cauta(treap &n,int val)
{if(n==nil) {fout<<0<<"\n";return ;}

 if(val<n->v)
     cauta(n->l,val);
     else if(val>n->v)
      cauta(n->r,val);
      else {fout<<1<<"\n";
      return;}
}

void cit()
{char x;
int no,i=1;
    ifstream fin("zeap.in");
    while( fin>>x)
    {

    if(x=='I')
        {fin>>no;
        insereaza(R,no);

        }
    if(x=='S')
        {fin>>no;

        sterge(R,no);
        }
    if(x=='C')
        {fin>>no;

        cauta(R,no);
        }
    if(x=='M')
        {fin>>x;

        if((R->l!=nil||R->r!=nil)&&R!=nil)
        {if(x=='I') fout<<R->difmin<<"\n";
        else fout<<R->max-R->min<<"\n";}
        else
         fout<<-1<<"\n";
        fin>>x;
        }
    }
}



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