/* greseli :
am luat 0 pentru ca am pus 10000 in loc de oo la prioritate
am luat 20 pentru ca afisam ce nu trebuia si primeam TLE
am luat 40 pentru ca am omis cand in treap este doar un nod
am luat 70 pntru ca nu am pus cazul cand in treap nu sunt noduri
si am luat 100 */
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     //  <=======================vezi ce face fara 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;
}