#include <cstdio>
#include <cstdlib>
#include <ctime>

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 *root,*nil;

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

inline void InitTreap()
{
	srand((unsigned int)(time(NULL)));
	root=nil=new Node;
	nil->left=nil;
	nil->right=nil;
}

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

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

inline void UpdateNode(Node *node)
{
	node->mindif=INF;
	if(node->left!=nil)
	{
		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!=nil)
	{
		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 *left=node->left;
	node->left=left->right;
	left->right=node;
	UpdateNode(node);
	UpdateNode(left);
	node=left;
}

inline void RotateLeft(Node *&node)
{
	Node *right=node->right;
	node->right=right->left;
	right->left=node;
	UpdateNode(node);
	UpdateNode(right);
	node=right;
}

inline void Balance(Node *&node)
{
	if(node->left->priority>node->priority)
	{
		RotateRight(node);
	}
	else if(node->right->priority>node->priority)
	{
		RotateLeft(node);
	}
}

int value,priority;

void Insert(Node *&node)
{
	if(node==nil)
	{
		node=new Node();
		node->priority=priority;
		node->value=value;
		node->min=node->max=value;
		return;
	}
	
	if(value<node->value)
	{
		Insert(node->left);
	}
	else
	{
		Insert(node->right);
	}

	Balance(node);

	UpdateNode(node);
}

int found;

void Erase(Node *&node)
{
	if(node==nil)
	{
		found=0;
		return;
	}
	if(node->value==value)
	{
		if(node->left==nil && node->right==nil)
		{
			found=1;
			delete node;
			node=nil;
		}
		else
		{
			if(node->left->priority<node->right->priority)
			{
				RotateLeft(node);
			}
			else
			{
				RotateRight(node);
			}
			
			Erase(node);
		}
	}
	else if(value<node->value)
	{
		Erase(node->left);
	}
	else
	{
		Erase(node->right);
	}
	
	UpdateNode(node);
}

void Search(Node *&node)
{
	if(node==nil)
	{
		found=0;
		return;
	}
	if(node->value==value)
	{
		found=1;
	}
	else if(value<node->value)
	{
		Search(node->left);
	}
	else
	{
		Search(node->right);
	}
}

int main()
{
	InitTreap();
	
	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')
		{
			value=Number();
			priority=rand()+1;
			Insert(root);
		}
		else if(*ptr=='S')
		{
			value=Number();
			Erase(root);
			if(!found)
			{
				fprintf(fout,"-1\n");
			}
		}
		else if(*ptr=='C')
		{
			value=Number();
			Search(root);
			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;
}