#include <cstdio>

using namespace std;

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

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

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()
{
	char *ptr=new char[8];
	while(fscanf(fin,"%s",ptr)!=EOF)
	{
		int val=0;
		if(*ptr=='I')
		{
			fscanf(fin,"%d",&val);
			root=Insert(root,val);
		}
		else if(*ptr=='S')
		{
			fscanf(fin,"%d",&val);
			root=Erase(root,val);
			if(!found)
			{
				fprintf(fout,"-1\n");
			}
		}
		else if(*ptr=='C')
		{
			fscanf(fin,"%d",&val);
			root=Search(root,val);
			fprintf(fout,"%d\n",found);
		}
		else if(*ptr=='M')
		{
			if(*(ptr+1)=='I')
			{
				fprintf(fout,"%d\n",MinDif(root));
			}
			else if(*(ptr+1)=='A')
			{
				fprintf(fout,"%d\n",MaxDif(root));
			}
		}
	}
	fclose(fin);
	fclose(fout);
	return 0;
}