using namespace std;
#include<iostream>
#include<fstream>
#include<cstdlib>
#include<ctime>
#define oo 0x3f3f3f3f
ofstream fout("zeap.out");
struct T{
	int key,p,min,max,difmin;
	T *l,*r;
	T(){}
	T(int key,int p,int min,int max,int difmin,T* l,T* r)
	 {
		 this->key=key;
		 this->p=p;
		 this->min=min;
		 this->max=max;
		 this->difmin=difmin;
		 this->l=l;
		 this->r=r;
	 }
};
T *R,*nil;

void init()
{
	R=nil=new T(-oo,-oo,oo,-oo,oo,NULL,NULL);
}

void rotleft(T* &n)
{ T* t=n->l;
n->l=t->r;
t->r=n;
n=t;

}

void rotright(T* &n)
{
	T* t=n->r;
	n->r=t->l;
	t->l=n;
	n=t;
}

void update(T* &n)
{
	if(n!=nil)
	{
		n->min=min(min(n->l->min,n->r->min),n->key);
		n->max=max(max(n->l->max,n->r->max),n->key);
		n->difmin= min(min(n->l->difmin,n->r->difmin),min(n->key-n->l->max,n->r->min-n->key));
		
	}		
}

void balance(T* &n)
{
	if(n->l->p>n->p) rotleft(n), update(n->r), update(n);
	if(n->r->p>n->p) rotright(n), update(n->l), update(n);
	
}

void insert(T* &n,int key)
{
	if(n==nil) {n=new T(key,rand(),key,key,oo,nil,nil); return;}
	if(key==n->key) return;
	if(key<n->key) insert(n->l,key);
	if(key>n->key) insert(n->r,key);
	
	update(n);
	balance(n);
	
}

void cauta(T* &n,int key)
{
	if(n==nil) {fout<<"0\n"; return;}
	
	if(key==n->key) {fout<<"1\n"; return;}
	if(key<n->key) cauta(n->l,key);
	if(key>n->key) cauta(n->r,key);
	
	
}

void erase(T* &n,int key)
{
	if(n==nil) {fout<<"-1\n"; return;}
	
	if(key<n->key) erase(n->l,key);
	if(key>n->key) erase(n->r,key);
	
	if(key==n->key)
	{
		if(n->l==nil && n->r==nil) 
		{delete n;
		n=nil;
		return;
		}
		
		else
		{
			if(n->l->p>n->r->p)
			{
				rotleft(n);
				update(n->r);
				update(n);
			}
			else
			{   rotright(n);
			    update(n->l);
				update(n);
			}
			erase(n,key);
		}
	}
	
	update(n);
}

void cit()
{
    char c;
    int x;
    int y=0;
    ifstream fin("zeap.in");
    while(fin>>c)
    {

        if(c=='I') {fin>>x; insert(R,x);}
        if(c=='S') {fin>>x; erase(R,x);}
        if(c=='C') {fin>>x; cauta(R,x);}
        if(c=='M') {
        fin>>c;fin>>c;
        if(R==nil ||(R->l==nil && R->r==nil))
           fout<<-1<<"\n";
          else
           if(c=='X')
              fout<<R->max - R->min<<"\n";
            else
              fout<<R->difmin<<"\n";

        }


    }
    fin.close();
}


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