#include<cstdio>
#include<cstring>

const char black='B', red='R';

struct NODE
{
	int v;
	char c;
	NODE *l,*r,*p;
};

typedef NODE* node;

node root;
int n;

void rotateLeft(node);
void rotateRight(node);
void insert(int);
void insertFix(node);
int remove(int);
void removeFix(node);
node successor(node);
char color(node x)
{
	if(x==NULL) return black;
	return x->c;
}
node grandP(node x)
{
	if(x->p!=NULL) return x->p->p;
	else return NULL;
}
node uncle(node x)
{
	node g = grandP(x);
	if(g==NULL) return NULL;
	if(g->l == x->p) return g->r;
	return g->l;
}
node parent(node x)
{
	return x->p;
}
node sibling(node x)
{
	if(x->p==NULL) return NULL;
	if(x->p->l==x) return x->p->r;
	return x->p->l;
}

void print(node n)
{
	if(n==NULL)
	{
		printf("N ");
		return;
	}
	printf("%d%c (",n->v,n->c);
	print(n->l);
	printf(",");
	print(n->r);
	printf(")");
}

int find(int v)
{
	node n = root;
	while(n!=NULL)
	{
		if(n->v == v) return 1;
		if(v < n->v) n = n->l;
		else n = n->r;
	}
	return 0;
}

int max()
{
	if(n<2) return -1;
	node n1,n2;
	n1 = n2 = root;
	while(n1->l != NULL) n1 = n1->l;
	while(n2->r != NULL) n2 = n2->r;
	return n2->v - n1->v;
}

int mindif(node r)
{
	int v1,v2;
	v1 = v2 = 0x7fffffff;
	if(r->l != NULL)
	{
		v1 = r->v - r->l->v;
		if(v1 == 1) return 1;
		v2 = mindif(r->l);
		if(v2<v1) v1=v2;
		if(v1==1) return 1;
	}
	if(r->r != NULL)
	{
		v2 = r->r->v - r->v;
		if(v2<v1) v1 = v2;
		if(v1==1) return 1;
		v2 = mindif(r->r);
		if(v2<v1) v1=v2;
		if(v1==1) return 1;
	}
	return v1;	
}

int min()
{
	if(n<2) return -1;
	node n1 = root;
	return mindif(n1);
}

int main()
{
	freopen("zeap.in","r",stdin);
	freopen("zeap.out","w",stdout);
	char a[1000];
	int v;
	while(!feof(stdin))
	{
		gets(a);
		switch(a[0])
		{
		case 'I':
			sscanf(a,"I %d",&v);
			insert(v);
			//print(root);printf("\n");
			break;
		case 'S':
			sscanf(a,"S %d",&v);
			if(remove(v))
			{
				printf("-1\n");
			}
			//print(root);printf("\n");
			break;
		case 'C':
			sscanf(a,"C %d",&v);
			printf("%d\n",find(v));
			break;
		default:
			if(a[1]=='I')
				printf("%d\n",min());
			else
				printf("%d\n",max());
			break;
		}
		scanf(" ");
	}
	return 0;
}

void rotateLeft(node n)
{
	node r = n->r;
	r->p = n->p;
	if(r->p == NULL)
		root = r;
	else
		if(n->p->l == n)
			n->p->l = r;
		else
			n->p->r = r;
	n->r = r->l;
	if(n->r != NULL)
		n->r->p = n;
	r->l = n;
	n->p = r;
}

void rotateRight(node n)
{
	node l = n->l;
	l->p = n->p;
	if(l->p == NULL)
		root = l;
	else
		if(n->p->l == n)
			n->p->l = l;
		else
			n->p->r = l;
	n->l = l->r;
	if(n->l != NULL)
		n->l->p = n;
	l->r = n;
	n->p = l;
}

void insert(int value)
{
	node i = root;
	if(root == NULL)
	{
		root = new NODE;
		root->c = black;
		root->v = value;
		root->l = root->p = root->r = NULL;
		++n;
		return;
	}
	for(i=root;;)
	{
		if(i->v == value) return;
		if(i->v > value)
			if(i->l == NULL) break;
			else
				i = i->l;
		else
			if(i->r == NULL) break;
			else
				i = i->r;
	}
	++n;
	node aux = new NODE;
	aux->v = value;
	aux->c = red;
	aux->r = aux->l = NULL;
	aux->p = i;
	if(value < i->v)
		i->l = aux;
	else
		i->r = aux;
	if(i->c == black) return;
	insertFix(aux);
}
void insertFix(node i)
{
	node g,u;
	while(true)
	{
		if(i==root)//case 1: root must be black => +1 on all paths if red
		{
			i->c = black;
			return;
		}
		if(color(i->p)==black) return;//reached a good state
		g = grandP(i);
		u = uncle(i);//parent is red => grandparent is black
		if(color(u)==red)
		{
			//		   black		 new i =red					or other sides for i and i->p and u
			//			/\					/ \
			//       red  red   =>		black black
			//		/					/
			//	 i=red				  red
			g->c = red;
			u->c = black;
			i->p->c = black;
			i=g;
		}
		else//uncle is black
			if(i->p == g->l)//left branch
			{
				//		black				 black					black=i
				//		/  \		    	/     \					/    \
				//	  red  black	=>   red=i   black   =>   i->p=red	 red(g)
				//		\				  / \							 /    \
				//		red = i	   i->p=red  1B							1B	 black(u)
				if(i->p->r == i)
					rotateLeft(i->p);
				g->l->c = black;
				g->c = red;
				rotateRight(g);
				return;
			}
			else
			{//same as above but on the right branch
				if(i->p->l == i)
					rotateRight(i->p);
				g->r->c = black;
				g->c = red;
				rotateLeft(g);
				return;
			}		
	}
}
int remove(int value)
{
	node i=root;
	if(i==NULL) return 1;
	for(;;)
	{
		if(i->v == value) break;
		if(i->v > value) i = i->l;
		else i = i->r;
		if(i==NULL) return 1;
	}
	node x = successor(i);
	if(x!=i)
	{
		i->v = x->v;
		i = x;
	}
	//delete i which now has at most one child
	--n;
	if(i->c == black)
		if(color(i->l)==red)
			i->l->c = black;
		else
			if(color(i->r)==red)
				i->r->c = black;
			else
				removeFix(i);
	node c = i->l == NULL? i->r : i->l;
	if(c!=NULL)
		c->p = i->p;
	if(i->p != NULL)
		if(i->p->l == i)
			i->p->l = c;
		else
			i->p->r = c;
	delete i;
	return 0;
}

void removeFix(node i)
{
	node p,s;
	for(;;)
	{
		if(i==root)//case 1 if we reached the root we color it black and we are done
		{
			if(root!=NULL)
				root->c = black;
			return;
		}
		p = parent(i);
		s = sibling(i);
		if(color(s)==red)//case 2: sibling is red we rotate towards i
		{
			s->c = black;
			p->c = red;
			if(p->l == i)
				rotateLeft(p);
			else
				rotateRight(p);
			//we loop again for i
		}
		else
			if(color(s)==black && color(s->l)==black && color(s->r)==black)//case 3 recolor the sibling
			{
				s->c = red;
				i = p; //loop for parent
			}
			else
				if(color(p)==red && color(s)==black && color(s->l)==black && color(s->r)==black)//case  4: red parent and children of s are black => recolor s and p
				{
					s->c = red;
					p->c = black;
					return;//made up for the missing node
				}
				else
					if(i == p->l)//cases depending on sides
					{
						if(color(s->l)==red)//case 5: red child of the sibling next to i
						{
							s->c = red;
							s->l->c = black;
							rotateRight(s);
						}
						//case 5 creates case 6
						s = sibling(i);
						s->c = p->c;
						p->c = black;
						s->r->c = black;
						rotateLeft(p);
						return;//made up for the missing node
					}
					else//case on right side
					{
						if(color(s->r)==red)//case 5: as above
						{
							s->c = red;
							s->r->c = black;
							rotateLeft(s);
						}
						s=sibling(i);
						s->c = p->c;
						p->c = black;
						s->l->c = black;
						rotateRight(p);
						return;//made up for the missing node
					}								
	}
}

node successor(node n)
{
	if(n->r == NULL) return n;
	n = n->r;
	while(n->l!=NULL)
		n = n->l;
	return n;
}