#include <stdio.h>  
 #include <algorithm>  
 #include <time.h>  
 #define max_pon 48234383  
 #define ms 1000000001  
   
 using namespace std;  
   
 struct treap  
 {  
     int key, prty, min, max, difm;  
     treap *l, *r;  
     treap(int key, int prty, int min, int max, int difm, treap *r, treap *l)  
     {  
         this->key = key, this->prty = prty, this->min = min, this->max = max;  
         this->difm = difm, this->r = r, this->l = l;  
     }  
 } *rad_tr, *nil;  
   
 int x, ct;  
 char oper, op2;  
   
 void calc(treap* &n)  
 {  
     n->min = min(n->key, n->l->min), n->max = max(n->key, n->r->max);  
     n->difm = min(min(n->r->difm, n->l->difm), min(n->r->min - n->key, n->key - n->l->max));  
 }  
   
 void rr(treap* &n)  
 {  
     treap *t = n->r;  
     n->r = t->l, t->l = n;  
     n = t;  
     if (n != nil && n->l != nil)  
         calc(n->l);  
 }  
   
 void rl(treap* &n)  
 {  
     treap *t = n->l;  
     n->l = t->r, t->r = n;  
     n = t;  
     if (n != nil && n->r != nil)  
         calc(n->r);  
 }  
   
 void balance(treap* &n)  
 {  
     if (n->r->prty > n->prty)  
         rr(n);  
     else if (n->l->prty > n->prty)  
         rl(n);  
     calc(n);  
 }  
   
 void insert_tr(treap* &n, int key, int pr)  
 {  
     if (n == nil)  
     {  
         n = new treap(key, pr, key, key, ms, nil, nil);  
         return;  
     }  
     if (key > n->key)  
         insert_tr(n->r, key, pr);  
     else if (key < n->key)  
         insert_tr(n->l, key, pr);  
     balance(n);  
 }  
   
 void erase_tr(treap* &n, int key)  
 {  
     if (n == nil)  
         return;  
     if (n->key > key)  
         erase_tr(n->l, key);  
     else if (n->key < key)  
         erase_tr(n->r, key);  
     else  
     {  
         if (n->l->prty > n->r->prty)  
             rl(n);  
         else rr(n);  
         if (n != nil)  
             erase_tr(n, key);  
         else  
         {  
             delete n->l;  
             n->l = NULL;  
             return;  
         }  
     }  
     calc(n);  
 }  
  
 int cauta_tr(treap *n, int key)  
 {  
     if (n == nil)  
         return 0;  
     if (n->key > key)  
         return cauta_tr(n->l, key);  
     else if (n->key < key)  
         return cauta_tr(n->r, key);  
     return 1;  
 }  
   
 int main()  
 {  
     srand(time(0));  
     freopen("zeap.in","r",stdin);  
     freopen("zeap.out","w",stdout);  
     rad_tr = nil = new treap(0, 0, ms, -ms, ms, NULL, NULL);  
     while (!feof(stdin))  
     {  
         scanf("%c", &oper);  
         if (oper != 'M')  
             scanf("%ld\n", &x);  
         else scanf("%c\n", &op2);  
         if (oper == 'I')  
         {  
             insert_tr(rad_tr, x, rand() % max_pon + 1);  
             ct++;  
         }  
         if (oper == 'S')  
             if (cauta_tr(rad_tr, x) == 1)  
             {  
                 ct--;  
                 erase_tr(rad_tr, x);  
             }  
             else printf("-1\n");  
         if (oper == 'C')  
             printf("%ld\n", cauta_tr(rad_tr, x));  
         if (oper == 'M' && ct < 2)  
             printf("-1\n");  
         else  
         {  
             if (oper == 'M' && op2 == 'A')  
                 printf("%ld\n", rad_tr->max - rad_tr->min);  
             if (oper == 'M' && op2 == 'I')  
                 printf("%ld\n", rad_tr->difm);  
         }  
     }  
     fclose(stdin);  
     fclose(stdout);  
     return 0;  
}