#include <cstdio>

#define file_in "zeap.in"
#define file_out "zeap.out"

struct nod{
	
	int val;
	nod * st, *dr;
};

nod * v;
int x,i;
char s[100];


void insereaza(nod *& c, int x){
	
	if (c){
		
		if (c->val==x)
			return;
		else
			if (c->val<x)
				insereaza(c->dr,x);
			else
				insereaza(c->st,x);
	}
	else{
		c=new nod;
		c->val=x;
		c->st=c->dr=0;
	}
}

void cmmd(nod *& c, nod *& f){
	if (f->dr)
		cmmd(c,f->dr);
	else{
		nod * man;
		c->val=f->val;
		man=f;
		f=f->st;
		delete man;
	}
}


void stergere(nod *& c, int x){
	
	nod * f;
	
	if (c){
		if (c->val==x)
			if (c->st==0 && c->dr==0){
				delete c;
				c=0;
			}
			else
			if (c->st==0){
                f=c->dr;
                delete c;
                c=f;
			}
			else
			if (c->dr==0){
                f=c->st;
                delete c;
                c=f;
			}	
			else
				cmmd(c,c->st);
		else
		if (c->val<x)
            stergere(c->dr,x);
		else
			stergere(c->st,x);
	}
	else
		return ;
}

int cautare(nod * c, int x){
	
	while(c){
		if (!c)
			return 0;
		if (c->val==x)
			return 1;
		else
			if (c->val<x)
				return cautare(c->dr,x);
			else
				return cautare(c->st,x);
	}
	
	return 0;
}

int main(){
	
	freopen(file_in,"r",stdin);
	freopen(file_out,"w",stdout);
	
	while(!feof(stdin)){
		gets(s);
		if (s[0]=='I'){
			x=0;
			i=2;
			while(s[i]>='0' && s[i]<='9'){
				x=x*10+s[i]-'0';
				i++;
			}
			insereaza(v,x);
		}
		else
		if (s[0]=='S'){
			x=0;
			i=2;
			while(s[i]>='0' && s[i]<='9'){
				x=x*10+s[i]-'0';
				i++;
			}
			if (!cautare(v,x))
				printf("-1\n");
			else
				stergere(v,x);
		}
		else
		if (s[0]=='C'){
			x=0;
			i=2;
			while(s[i]>='0' && s[i]<='9'){
				x=x*10+s[i]-'0';
				i++;
			}
			printf("%d\n", cautare(v,x));
		}
		else
		if (s[0]=='M' && s[1]=='A'){
			nod * a=v;
			nod * b=v;
			while(a->st) a=a->st;
			while(b->dr) b=b->dr;
			if (!b || !a)
				printf("-1\n");
			else
			printf("%d\n", b->val-a->val);
		}
		else{
			nod * z=v;
			while(z->st) z=z->st;
			nod * b=z->dr;
			if (!b)
				printf("-1\n");
			else
			printf("%d\n", b->val-z->val);
		}
		
	}
	
	return 0;
}