#include <cstdio>

using namespace std;

const char InFile[]="zeap.in";
const char OutFile[]="zeap.out";
const int MaxBufferSize=1024*1024*5;
const int INF=1<<30;

FILE *fin=fopen(InFile,"r");
FILE *fout=fopen(OutFile,"w");

char buffer[MaxBufferSize],*ptr=buffer;

inline void SkipWS()
{
	while(!(('0'<=*ptr && *ptr<='9')||('A'<=*ptr && *ptr<='Z')))
	{
		if(*ptr==0)
		{
			return;
		}
		++ptr;
	}
}

inline int Number()
{
	int sol=0;
	while(!('0'<=*ptr && *ptr<='9'))
	{
		++ptr;
	}
	
	while('0'<=*ptr && *ptr<='9')
	{
		sol*=10;
		sol+=*ptr-'0';
		++ptr;
	}
	return sol;
}

struct Node
{
	Node(int value=0, int mindif=INF, int min=INF, int max=0, Node *parent=NULL, Node *left=NULL, Node *right=NULL): value(value), mindif(mindif), min(min), max(max), parent(parent), left(left), right(right){}
	
	int value,mindif,min,max;
	
	Node *parent,*left,*right;
};

inline int MinDif(Node *node)
{
	if(!node)
	{
		return -1;
	}
	if(!node->left && !node->right)
	{
		return -1;
	}
	return node->mindif;
}

inline int MaxDif(Node *node)
{
	if(!node)
	{
		return -1;
	}
	if(!node->left && !node->right)
	{
		return -1;
	}
	return node->max-node->min;
}

inline void UpdateNode(Node *node)
{
	node->mindif=INF;
	if(node->left)
	{
		node->min=node->left->min;
		if(node->mindif>node->left->mindif)
		{
			node->mindif=node->left->mindif;
		}
		int val=node->value-node->left->max;
		if(node->mindif>val)
		{
			node->mindif=val;
		}
	}
	else
	{
		node->min=node->value;
	}
	
	if(node->right)
	{
		node->max=node->right->max;
		if(node->mindif>node->right->mindif)
		{
			node->mindif=node->right->mindif;
		}
		int val=node->right->min-node->value;
		if(node->mindif>val)
		{
			node->mindif=val;
		}
	}
	else
	{
		node->max=node->value;
	}
}

inline void RotateRight(Node *node)
{
	Node *x=node->left;
	node->left=x->right;
	if(x->right)
	{
		x->right->parent=node;
	}
	x->right=node;
	if(node->parent)
	{
		if(node->parent->right==node)
		{
			node->parent->right=x;
		}
		else
		{
			node->parent->left=x;
		}
	}
	x->parent=node->parent;
	node->parent=x;
	UpdateNode(node);
	UpdateNode(x);
}

inline void RotateLeft(Node *node)
{
	Node *x=node->right;
	node->right=x->left;
	if(x->left)
	{
		x->left->parent=node;
	}
	x->left=node;
	if(node->parent)
	{
		if(node->parent->right==node)
		{
			node->parent->right=x;
		}
		else
		{
			node->parent->left=x;
		}
	}
	x->parent=node->parent;
	node->parent=x;
	UpdateNode(node);
	UpdateNode(x);
}

inline void Splay(Node *node)
{
	if(!node)
	{
		return;
	}
	while(node->parent)
	{
		Node *p=node->parent;
		Node *g=p->parent;
		if(g==NULL)
		{
			if(p->left==node)
			{
				RotateRight(p);
			}
			else
			{
				RotateLeft(p);
			}
		}
		else
		{
			if(node==p->left&&p==g->left)
			{
				RotateRight(g);
				RotateRight(p);
			}
			else if(node==p->right&&p==g->right)
			{
				RotateLeft(g);
				RotateLeft(p);
			}
			else if(node==p->left&&p==g->right)
			{
				RotateRight(p);
				RotateLeft(g);
			}
			else
			{
				RotateLeft(p);
				RotateRight(g);
			}
		}
	}
}

inline Node* Insert(Node *node, int value)
{
	if(!node)
	{
		node=new Node();
		node->value=value;
		node->min=value;
		node->max=value;
	}
	else
	{
		while(1)
		{
			if(value==node->value)
			{
				Splay(node);
				break;
			}
			else if(value<node->value)
			{
				if(node->left)
				{
					node=node->left;
				}
				else
				{
					node->left=new Node();
					node->left->parent=node;
					UpdateNode(node);
					node=node->left;
					node->value=value;
					node->min=node->max=value;
					break;
				}
			}
			else
			{
				if(node->right)
				{
					node=node->right;
				}
				else
				{
					node->right=new Node();
					node->right->parent=node;
					UpdateNode(node);
					node=node->right;
					node->value=value;
					node->min=node->max=value;
					break;
				}
			}
		}
		Splay(node);
	}
	return node;
}

int found;

inline Node* Erase(Node *node, int value)
{
	found=0;
	Node *x=NULL;
	while(node)
	{
		x=node;
		if(node->value==value)
		{
			break;
		}
		if(value<node->value)
		{
			node=node->left;
		}
		else
		{
			node=node->right;
		}
	}
	if(node)
	{
		found=1;
		if(!node->left && !node->right)
		{
			if(node->parent)
			{
				if(node->parent->left==node)
				{
					node->parent->left=NULL;
				}
				else
				{
					node->parent->right=NULL;
				}
			}
			delete node;
		}
		else if(!node->left)
		{
			x=node->right;
			if(node->parent)
			{
				if(node->parent->left==node)
				{
					node->parent->left=node->right;
				}
				else
				{
					node->parent->right=node->right;
				}
				node->right->parent=node->parent;
			}
			delete node;
		}
		else if(!node->right)
		{
			x=node->left;
			if(node->parent)
			{
				if(node->parent->left==node)
				{
					node->parent->left=node->left;
				}
				else
				{
					node->parent->right=node->left;
				}
				node->left->parent=node->parent;
			}
			delete node;
		}
		else
		{
			Node *temp=node->left;
			while(temp->right)
			{
				temp=temp->right;
			}
			node->value=temp->value;
			x=temp->parent;
			if(x->left==temp)
			{
				x->left=NULL;
			}
			else
			{
				x->right=NULL;
			}
		}
	}
	Splay(x);
	return x;
}

inline Node* Search(Node *node, int value)
{
	found=0;
	if(!node)
	{
		return NULL;
	}
	else
	{
		Node *temp=NULL;
		while(node)
		{
			if(node->value==value)
			{
				found=1;
				Splay(node);
				return node;
			}
			else if(value<node->value)
			{
				temp=node;
				node=node->left;
			}
			else
			{
				temp=node;
				node=node->right;
			}
		}
		Splay(temp);
		return temp;
	}
}

Node *root=NULL;

int main()
{
	
	fseek(fin,0,SEEK_END);
	int size=ftell(fin);
	rewind(fin);
	
	fread(buffer,1,size,fin);
	buffer[++size]=0;
	fclose(fin);
	
	while(*ptr)
	{
		if(*ptr=='I')
		{
			root=Insert(root,Number());
		}
		else if(*ptr=='S')
		{
			root=Erase(root,Number());
			if(!found)
			{
				fprintf(fout,"-1\n");
			}
		}
		else if(*ptr=='C')
		{
			root=Search(root,Number());
			fprintf(fout,"%d\n",found);
		}
		else if(*ptr=='M')
		{
			++ptr;
			if(*ptr=='I')
			{
				fprintf(fout,"%d\n",MinDif(root));
			}
			else if(*ptr=='A')
			{
				fprintf(fout,"%d\n",MaxDif(root));
			}
			ptr+=2;
		}
		SkipWS();
	}
	
	fclose(fout);
	return 0;
}