using namespace std;

#include<iostream>
#include<fstream>
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->r->min);
    n->max=max(n->l->max,n->r->max);
    n->difmin=min(min(n->l->difmin,n->r->difmin),min(n->v-n->l->max,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);
}
void insereaza(treap &n,int val)
{
    if(n==nil)
    {n->r=nil;
    n->l=nil;
    n->difmin=oo;
    n->h=1;
    n->min=n->max=n->v=val;
    return;
    }
    if(val>n->v)
        insereaza(n->r,val);
    if(val<n->v)
        insereaza(n->l,val);
    balance(n);
    update(n);
}
void sterge(treap& n,int val)
{
    if(n==nil) {fout<<"-1";return ;}
    if(n->v>val)
       return 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) ;
         }
     update(n);
}

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

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

void cit()
{char x;
int no;
    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(x='I') fout<<R->difmin;
        else fout<<R->max-R->min;
        fin>>x;
        }
    }
}



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