# include <stdio.h>
# include <stdlib.h>

const long int MAXN=300000;

typedef struct NOD
        {
        long int val;
        long int indexh;
        long int range;
        long int height;
        NOD *stga,*drta,*tata;
        };

typedef struct HEAP
        {
        long int len;
        NOD *v[MAXN+1];
        };
        
HEAP heap;
NOD *root;

//////
// DEBUG
//////

void scrie_NOD(NOD *root, long int spaces)
{
     long int i;
     for (i=1;i<=spaces;i++)
         printf(" ");
     printf("%ld",root->val);
     if (root->tata) printf("-%ld\n",root->tata->val);
     else printf("-\"\n");
     if (root->stga) scrie_NOD(root->stga,spaces+1);
     if (root->drta) scrie_NOD(root->drta,spaces+1);
}

void debug()
{
     scrie_NOD(root,0);
     fflush(stdin);
     getchar();
}
        
////////////
// FUNCTII PT HEAP
////////////

long int better_heap(NOD *a, NOD *b)
{
     if (a->range<b->range) return 1;
     return 0;
}

void float_heap(HEAP &heap, long int i)
{
     NOD *aux;
     while (i/2&&better_heap(heap.v[i],heap.v[i/2]))
           {
           aux=heap.v[i];
           heap.v[i]=heap.v[i/2];
           heap.v[i/2]=aux;
           heap.v[i]->indexh=i;
           heap.v[i/2]->indexh=i/2;
           i/=2;
           }
}

void submerge_heap(HEAP &heap, long int i)
{
     NOD *aux;
     long int min;
     do
       {
       min=i;
       if (2*i  <=heap.len&&better_heap(heap.v[2*i  ],heap.v[min])) min=2*i  ;
       if (2*i+1<=heap.len&&better_heap(heap.v[2*i+1],heap.v[min])) min=2*i+1;
       if (min==i) break;
       aux=heap.v[i];
       heap.v[i]=heap.v[min];
       heap.v[min]=aux;
       heap.v[i]->indexh=i;
       heap.v[min]->indexh=min;
       i=min;
       }
     while (1);
}

void insert_heap(HEAP &heap, NOD *a)
{
     heap.len++;
     heap.v[heap.len]=a;
     a->indexh=heap.len;
     float_heap(heap,heap.len);
}

void extract_heap(HEAP &heap, NOD* a)
{
     heap.v[a->indexh]=heap.v[heap.len];
     heap.len--;
     heap.v[a->indexh]->indexh=a->indexh;
     submerge_heap(heap,a->indexh);
     a->indexh=0;
}

///////////////
// FUNCTII PT ARBORE
///////////////

long int get_height(NOD *root)
{
     if (root==NULL) return 0;
     long int st=0,dr=0;
     if (root->stga) st=root->stga->height;
     if (root->drta) dr=root->drta->height;
     if (st<dr) root->height=dr+1;
     else root->height=st+1;
     return root->height;
}    

void rotate_left(NOD *&root, NOD *nod)
{
     NOD *fiu=nod->drta; 
     if (fiu==NULL) return;
     fiu->tata=nod->tata;
     if (fiu->tata)
        if (fiu->tata->drta==nod) fiu->tata->drta=fiu;
        else fiu->tata->stga=fiu;
     else root=fiu;
     nod->tata=fiu;
     nod->drta=fiu->stga;
     fiu->stga=nod;
     if (nod->drta) nod->drta->tata=nod;
     get_height(nod);
     get_height(fiu);
}

void rotate_right(NOD *&root, NOD *nod)
{
     NOD *fiu=nod->stga;
     if (fiu==NULL) return;
     fiu->tata=nod->tata;
     if (fiu->tata)
        if (fiu->tata->drta==nod) fiu->tata->drta=fiu;
        else fiu->tata->stga=fiu;
     else root=fiu;
     nod->tata=fiu;
     nod->stga=fiu->drta;
     fiu->drta=nod;
     if (nod->stga) nod->stga->tata=nod;
     get_height(nod);
     get_height(fiu);
}

void rotate_right_left(NOD *&root, NOD *nod)
{
     if (nod==NULL || nod->drta==NULL) return;
     rotate_right(root,nod->drta);
     rotate_left(root,nod);
}

void rotate_left_right(NOD *&root, NOD *nod)
{
     if (nod==NULL || nod->stga==NULL) return;
     rotate_left(root,nod->stga);
     rotate_right(root,nod);
}

void balance(NOD *&root, NOD *nod)
{
     long int hs,hd;
     hs=get_height(nod->stga);
     hd=get_height(nod->drta);
     if (hs-hd==2)
        if (get_height(nod->stga->stga)>get_height(nod->stga->drta)) rotate_right(root,nod);
        else rotate_left_right(root,nod);
     if (hd-hs==2)
        if (get_height(nod->drta->drta)>get_height(nod->drta->stga)) rotate_left(root,nod);
        else rotate_right_left(root,nod);
     if (nod->tata) balance(root,nod->tata);
}

long int minim_arbore(NOD *root)
{
     if (root==NULL) return 0;
     if (root->stga==NULL) return root->val;
     else return minim_arbore(root->stga);
}

long int maxim_arbore(NOD *root)
{
     if (root==NULL) return 0;
     if (root->drta==NULL) return root->val;
     else return maxim_arbore(root->drta);
}

NOD* next_arbore(NOD *root)
{
     if (root->drta)
        {
        root=root->drta;
        while (root->stga) root=root->stga;
        return root;
        }
     while (root->tata && root->tata->drta==root) root=root->tata;
     return root->tata;
}

NOD* prev_arbore(NOD *root)
{
     if (root->stga)
        {
        root=root->stga;
        while (root->drta) root=root->drta;
        return root;
        }
     while (root->tata && root->tata->stga==root) root=root->tata;
     return root->tata;
}

NOD* exista(NOD *root, long int val)
{
     if (root==NULL) return NULL;
     if (root->val==val) return root;
     if (root->val<val) return exista(root->drta,val);
     return exista(root->stga,val);
}

NOD *make(long int val, long int indexh, long int range,long int height, NOD *stga, NOD *drta, NOD *tata)
{
    NOD *p=(NOD*) malloc (sizeof(NOD));
    p->val=val;
    p->indexh=indexh;
    p->range=range;
    p->stga=stga;
    p->drta=drta;
    p->tata=tata;
    p->height=height;
    return p;
}

void insereaza(NOD *&root, long int val)
{
     if (root&&exista(root,val)) return;
     if (root==NULL) 
        {
        root=make(val,0,-1,1,NULL,NULL,NULL);
        return;
        }
     NOD *nod=root,*tata=NULL;
     //cautam locul unde trebuie inserat
     while (nod)
           {
           if (nod->val>val) 
              {
              tata=nod;
              nod=nod->stga;
              }
           else
               {
               tata=nod;
               nod=nod->drta;
               }
           }
     if (tata->val<val) 
        {
        tata->drta=make(val,0,0,1,NULL,NULL,tata);
        nod=tata->drta;
        }
     else
         {
         tata->stga=make(val,0,0,1,NULL,NULL,tata);
         nod=tata->stga;
         }  
     
     //printf("Inainte de rotatii\n");    
     //debug();
         
     NOD *previous=prev_arbore(nod);
     if (previous) 
        {
        if (previous->indexh) extract_heap(heap,previous);
        previous->range=nod->val-previous->val;
        insert_heap(heap,previous);
        }
     NOD *next=next_arbore(nod);
     if (next)
        {
        nod->range=next->val-nod->val;
        insert_heap(heap,nod);
        }
     nod->height=get_height(nod);
     balance(root,nod);
     //debug();
}

void sterge(NOD *&root, NOD *nod, long int modheap)
{
     //intai il scoatem din HEAP daca e cazul sa fie acolo
     NOD *tata,*prev,*next;
     if (modheap)
        {
     prev=prev_arbore(nod);
     next=next_arbore(nod);
     if (nod->indexh)
        {
        extract_heap(heap,nod);
        }
     if (prev && next)
        {
        extract_heap(heap,prev);
        prev->range=next->val-prev->val;
        insert_heap(heap,prev);
        }
     else if (prev && next==NULL)
          {
          extract_heap(heap,prev);
          }
        }
     //am rezolvat cu heapul, acuma scoatem din arbore
     if (nod->stga==NULL && nod->drta==NULL)
        {
        if (nod->tata)
           {
           tata=nod->tata;
           if (nod->tata->stga==nod) 
              {
              nod->tata->stga=NULL;
              free(nod);
              }
           else
               {
               nod->tata->drta=NULL;
               free(nod);
               }
           balance(root,tata);
           }
        else 
             {
             root=NULL;
             free(nod);
             }
        }
     else if (nod->stga==NULL || nod->drta==NULL)
          {
          NOD *fiu;
          if (nod->stga==NULL) fiu=nod->drta;
          else fiu=nod->stga;
          if (nod->tata)
             {
             tata=nod->tata;
             if (nod->tata->stga==nod)
                nod->tata->stga=fiu;
             else 
                  nod->tata->drta=fiu;
             fiu->tata=tata;
             balance(root,tata);
             }
          else
              root=fiu;
          free(nod);
          }
     else
         {
         next=next_arbore(nod);
         nod->val=next->val;
         nod->indexh=next->indexh;
         nod->range=next->range;
         nod->height=next->height;
         sterge(root,next,0);
         }
}
          
long int run_sterge(long int val)
{
     NOD *nod=exista(root,val);
     if (nod==NULL) return -1;
     sterge(root,nod,1);
     return 0;
}

long int run_cauta(long int val)
{
     NOD *nod=exista(root,val);
     if (nod==NULL) return 0;
     return 1;
}

long int run_min()
{
     if (heap.len==0) return -1;
     return heap.v[1]->range;
}

long int run_max()
{
     if (heap.len==0) return -1;
     return maxim_arbore(root)-minim_arbore(root);
}     

int main()
{
    FILE *f=fopen("zeap.in","r");
    FILE *g=fopen("zeap.out","w");
    char buff[100],*test;
    long int nr,ok;
    do
      {
      test=fgets(buff,100,f);
      if (test==NULL) break;
      if (buff[0]=='I') 
         {
         sscanf(buff+1,"%ld",&nr);
         insereaza(root,nr);
         }
      if (buff[0]=='C')
         {
         sscanf(buff+1,"%ld",&nr);
         fprintf(g,"%ld\n",run_cauta(nr));
         }
      if (buff[0]=='S')
         {
         sscanf(buff+1,"%ld",&nr);
         ok=run_sterge(nr);
         if (ok==-1) fprintf(g,"%ld\n",ok);
         }
      if (buff[0]=='M'&&buff[1]=='I')
         fprintf(g,"%ld\n",run_min());
      if (buff[0]=='M'&&buff[1]=='A')
         fprintf(g,"%ld\n",run_max());
      //debug();
      }
    while(1);
    fclose(f);
    fclose(g);
    return 0;
}