#include <cstdio>
#include <cstdlib>
#include <cstring>

#define MAX_INT ~(1<<31)
#define MAX_FILE_SIZE 5000000
#define min(a,b) (a) < (b) ? (a) : (b)
#define max(a,b) (a) > (b) ? (a) : (b)

enum
{
 SEARCH = 'C',
 INSERT = 'I',
 ERASE = 'S',
 DMAX = 'X' + 'A' * 128 + 'M' * 128 * 128,
 DMIN = 'N' + 'I' * 128 + 'M' * 128 * 128
};

class myAVL {

        public:

        struct node
        {
         int data, dmin, h;
         node *l, *r, *pred, *succ, *fi, *la;

         node(int data1, int dmin1, int h1, node *l1, node *r1, node *pred1, node *succ1, node *fi1, node *la1) :
            data(data1), dmin(dmin1), h(h1),
             l(l1), r(r1), pred(pred1), succ(succ1), fi(fi1), la(la1) {}
        };
        

        node *root, *NIL;
        int size;


        myAVL()
        {
         root = NIL = new node(0,MAX_INT,-1,0,0,0,0,0,0);
         size = 0;
        }

        int getMin(node * p)
        {
         return p->dmin;
        }

        int getMax(node * p)
        {
         return p->la->data - p->fi->data;
        }
        
        int calcMin(node * p)
        {
         int minn = min(p->l->dmin,p->r->dmin);
         if(p->pred != NIL & p->pred->h < p->h)
          minn = min(p->data - p->pred->data, minn);
         if(p->succ != NIL & p->succ->h < p->h)
          minn = min(p->succ->data - p->data, minn);
         return minn;
        }

        void update_info(node * &p)
        {
         if(p->l != NIL) p->fi = p->l->fi;
          else p->fi = p;
         if(p->r != NIL) p->la = p->r->la;
          else p->la = p;
         p->dmin = calcMin(p);
        }

        inline int geth(node * p)
        {
         return (max(p->l->h,p->r->h) ) + 1;
        }

        node * rotright(node * p)
        {
         node * t = p->l;

         p->l = t->r;
         t->r = p;

         p->h = geth(p); t->h = geth(t);

         update_info(p); update_info(t);
         
         return t;

        }

        node * rotleft(node * p)
        {
         node * t = p->r;

         p->r = t->l;

         t->l = p;

         p->h = geth(p); t->h = geth(t);

         update_info(p); update_info(t);

         return t;
         
        }

        node * balance(node * p)
        {

         if(p->r->h == p->l->h + 2)
         {
          if(p->r->l->h > p->r->r->h)
           p->r = rotright(p->r);
          p = rotleft(p);
         }


         if(p->r->h == p->l->h - 2)
         {
          if(p->l->r->h > p->l->l->h)
           p->l = rotleft(p->l);
          p = rotright(p);
         }

         p->h = geth(p);
         
         return p;
        }

        node * insert(node * p, node * pr, node * su, int key)
        {
          if(p == NIL)
          {
           p = new node(key,MAX_INT,0,NIL,NIL,pr,su,NIL,NIL);

           p->fi = p->la = p;

           if(pr != NIL) pr->succ = p;
           if(su != NIL) su->pred = p;

           ++size;

           return p;
          }
           else
           {
            if(key == p->data) return p;
             else
              if(key < p->data) p->l = insert(p->l,pr,p,key);
               else p->r = insert(p->r,p,su,key);

            update_info(p);
               //printf("Data = %d St = %d Dr= %d h(p)= %d h(p->l)= %d h(p->r)  %d\n",
                //p->data,p->l->data,p->r->data,p->h,p->l->h,p->r->h);
               // geth(p);
                //for(int i = 0 ; i <= 100; ++i) printf("-"); printf("\n");
                //debug(p);
            return balance(p);
           }
        }

        
        node * erase(node * p,int & found, int key)
        {
         if(p == NIL)
           { found = 0; return p; }
          else
          {
           if(p->data == key)
           {
            if(p->l == NIL | p->r == NIL)
            {
             node * t = p->l == NIL ? p->r : p->l;

             p->pred->succ = p->succ;
             p->succ->pred = p->pred;

             --size;

             free(p);
             return t;
            }

            node *t;
            for(t = p->r; t->l != NIL; t = t->l);

              p->data = t->data;
              
              p->r = erase(p->r,found,t->data);
            

           }
           
           else
            if(key < p->data) p->l = erase(p->l,found,key);
             else p->r = erase(p->r,found,key);

            if(found) update_info(p);
             
           return balance(p);
           
          }
        }


        int search(node * p,int key)
        {
         if(p == NIL) return 0;

         if(p->data == key) return 1;

         if(key < p->data) return search(p->l,key);
            else return search(p->r,key);
        }


        void debug(myAVL::node * p)
        {
        if(p != 0)
        {
        debug(p->l);


        printf("Data = %d Dmin = %d H = %d",p->data,p->dmin,p->h);
        printf(" L = %d R = %d Pr = %d Succ = %d Fi = %d La = %d\n",p->l->data,p->r->data,p->pred->data,p->succ->data,p->fi->data,p->la->data);


        debug(p->r);
         }
        }

};


char * init_inbuf() {

        char * buf = (char*) malloc ( MAX_FILE_SIZE );
        freopen("zeap.in","r",stdin);
        fread(buf,sizeof(char),MAX_FILE_SIZE,stdin);

        return buf;
}

char * init_outbuf() {

        char * buf = (char*) malloc( MAX_FILE_SIZE / 2 );
        freopen("zeap.out","w",stdout);
        setbuf(stdout,buf);

        return buf;
}

int getOp(char * &buf) {

        buf += strspn(buf," \n\t");

        if(*buf == '\0') return -1;

        int code = 0;
        while(*buf >= 'A' && *buf <= 'Z')
        {
         code = code * 128 + *buf; ++buf;
        }

        return code;
}



int getVal(char * &buf) {

        buf += strspn(buf," \n\t");

        if(*buf == '\0') return -1;

        int num = 0;
        while(*buf >= '0' & *buf <= '9')
        {
         num = num * 10 + *buf - '0'; ++buf;

        }

        buf += strspn(buf," \n\t");

        return num ? num : -1;
}

void write_buf(char * &buf) {

        fflush(stdout);
}

int main() {

        char * inbuf = init_inbuf(), * outbuf = init_outbuf();

        myAVL  * avl = new myAVL();

        int op,val,found;
        while(*inbuf) {

          op = getOp(inbuf); val = getVal(inbuf);
          
          switch(op) {
          case SEARCH: printf("%d\n",avl->search(avl->root, val) ); break;

          case INSERT: avl->root = avl->insert(avl->root,avl->NIL,avl->NIL,val); break;

          case ERASE:  found = 1;
                       avl->root = avl->erase(avl->root,found,val);
                       if(!found)
                        printf("-1\n");
                       break;

          case DMAX: avl->size>=2 ? printf("%d\n",avl->getMax(avl->root)) : -1; break;

          case DMIN: avl->size>=2 ? printf("%d\n",avl->getMin(avl->root)) : -1; break;
          }
          //for(int i = 0 ; i <= 100; ++i) printf("-"); printf("\n");
          //avl->debug(avl->root);
        }

        write_buf(outbuf);

        return 0;
}