#include<stdio.h>
#include<cstdlib>
#include<ctime>

FILE*f=fopen("zeap.in","r");
FILE*g=fopen("zeap.out","w");

const int INF = 1<<29;

struct node{
	int key,priority;
	int max,min,min_dif;
	node *ls,*rs;
	
	node () {
		key = priority = 0;
		max = min = min_dif = 0;
		ls = rs = NULL;
	}
	
	node ( int _key , int _priority , node *_ls , node *_rs ){
		key =_key;
		priority = _priority;
		ls = _ls;
		rs = _rs;
		max = min = key; min_dif = INF;
	}
};

node *R,*nul;

inline int min ( const int &a , const int &b ){
	return a <= b ? a : b;
}

inline int max ( const int &a , const int &b ){
	return a >= b ? a : b;
}

inline void update ( node* &nod ){
	
	nod->min = nod->max = nod->key; nod->min_dif = INF;
	if ( nod->ls != nul ){
		nod->min = min(nod->min,nod->ls->min);
		nod->max = max(nod->max,nod->ls->max);
		nod->min_dif = min(nod->min_dif,nod->key - nod->ls->max);
		nod->min_dif = min(nod->min_dif,nod->ls->min_dif);
	}
	if ( nod->rs != nul ){
		nod->min = min(nod->min,nod->rs->min);
		nod->max = max(nod->max,nod->rs->max);
		nod->min_dif = min(nod->min_dif,nod->rs->min - nod->key);
		nod->min_dif = min(nod->min_dif,nod->rs->min_dif);
	}
}

inline void rotate_ls ( node* &nod ){
	node *fiu = nod->ls;
	nod->ls = fiu->rs;
	fiu->rs = nod;
	update(nod); update(fiu);
	nod = fiu;
}

inline void rotate_rs ( node* &nod ){
	node *fiu = nod->rs;
	nod->rs = fiu->ls;
	fiu->ls = nod;
	update(nod); update(fiu);
	nod = fiu;
}

inline void balance ( node* &nod ){
	
	if ( nod->ls->priority > nod->priority ){
		rotate_ls(nod);
	}
	else{
		if ( nod->rs->priority > nod->priority ){
			rotate_rs(nod);
		}
	}
}

void insert ( node* &nod , int key , int priority ){
	
	if ( nod == nul ){
		nod = new node(key,priority,nul,nul);
		return ;
	}
	
	if ( key < nod->key ){
		insert(nod->ls,key,priority);
	}
	else{
		if ( key > nod->key ){
			insert(nod->rs,key,priority);
		}
	}
	
	balance(nod);
	
	update(nod);
}

int erase ( node* &nod , int key ){
	if ( nod == nul ){
		return -1; 
	}
	
	int return_val;
	if ( nod->key > key ){
		return_val = erase(nod->ls,key);
	}
	else{
		if ( nod->key < key ){
			return_val = erase(nod->rs,key);
		}
		else{
			if ( nod->ls == nul && nod->rs == nul ){
				return_val = 1;
				delete nod; nod = nul;
			}
			else{
				if ( nod->ls->priority > nod->rs->priority ){
					rotate_ls(nod);
				}
				else{
					rotate_rs(nod);
				}
				return_val = erase(nod,key);
			}
		}
	}
	
	return return_val;
}

int search ( node* &nod , int val ){
	
	if ( nod == nul ){
		return 0;
	}
	if ( nod->key == val ){
		return 1;
	}
	
	if ( val < nod->key ){
		return search(nod->ls,val);
	}
	else{
		return search(nod->rs,val);
	}
}

int main () {
	
	srand(time(NULL));
	R = nul = new node(0,0,nul,nul);
	
	char op;
	while ( fscanf(f,"%c",&op) != EOF ){
		
		if ( op == 'I' ){
			int x;
			fscanf(f,"%d\n",&x);
			insert(R,x,rand()+1);
		}
		else{
			if ( op == 'S' ){
				int x;
				fscanf(f,"%d\n",&x);
				int return_val = erase(R,x);
				if ( return_val == -1 ){
					fprintf(g,"%d\n",-1);
				}
			}
			else{
				if ( op == 'C' ){
					int x;
					fscanf(f,"%d\n",&x);
					fprintf(g,"%d\n",search(R,x));
				}
				else{
					char a,b;
					fscanf(f,"%c%c\n",&a,&b);
					if ( a == 'A' && b == 'X' ){
						int res = R->max - R->min; if ( !res )	res = -1;
						fprintf(g,"%d\n",res);
					}
					else{
						int res = R->min_dif;
						if ( res == INF ){
							res = -1;
						}
						fprintf(g,"%d\n",res);
					}
				}
			}
		}
	}
	
	fclose(f);
	fclose(g);
	
	return 0;
}