#include <bits/stdc++.h>

using namespace std;

ifstream in("zeap.in");
ofstream out("zeap.out");

const int MOD=666013;
struct node{
	node *l, *r;
	int key,priority,minn,mxx,minndif;

	node(node *le,node *ri,int val,int prior,int minim,int maxim,int mnndif){
		this->l=le;
		this->r=ri;
		key=val;
		priority=prior;
		minn=minim;
		mxx=maxim;
		minndif=mnndif;
	}
} *rad,*nule;

bool search(node *&n,int x)
{
	if(n==nule) return 0;
	if(n->key==x) return 1;
	if(n->key > x) return search(n->l,x);
	return search(n->r,x);
}

int maxdif(node *&n)
{
	if(n->mxx >n->minn) return n->mxx - n->minn;
	return -1;
}


int mindif(node *&n)
{	
	if(n->minndif>0 && n->minndif < INT_MAX-1000)
		return n->minndif;
	return -1;
}

void remax(node *&n)
{
	if(n==nule) return;
	n->mxx = n->key;
	n->minn = n->key;
	n->minndif=INT_MAX-1000;
	if(n->l != nule)
	{
		n->mxx = max(n->mxx ,n->l->mxx);
		n->minn=min(n->minn,n->l->minn);
		n->minndif=min(n->minndif,min(n->l->minndif,n->key - n->l->mxx));
	}
	if(n->r != nule)
	{
		n->mxx = max(n->mxx, n->r->mxx);
		n->minn = min(n->minn, n->r->minn);
		n->minndif=min(n->minndif,min(n->r->minndif,n->r->minn - n->key));
	}
}

void L(node *&n)
{
	remax(n);
	node *aux=n->l;
	n->l=aux->r;
	aux->r=n;
	n=aux;
	remax(n->l);
	remax(n->r);
	remax(n);
}

void R(node *&n)
{
	remax(n);
	node *aux=n->r;
	n->r=aux->l;
	aux->l=n;
	n=aux;
	remax(n->l);
	remax(n->r);
	remax(n);
}

void balance(node *&n)
{
	if(n==nule) return;
	remax(n);
	if(n->l!=nule && n->l->priority > n->priority) L(n);
	if(n->r!=nule && n->r->priority > n->priority) R(n);
}


void insert(node *&n,int val,int priority)
{
	if(n==nule)
	{
		n=new node(nule,nule,val,priority,val,val,INT_MAX-1000);
		return;
	}
	if(n->key > val) insert(n->l,val,priority);
	else insert(n->r,val,priority);
	balance(n);
}


void erase(node *&n,int val)
{
	if(n->key > val) erase(n->l,val);
	else if(n->key < val) erase(n->r,val);
	else
	{
		if(n->l==nule && n->r==nule)
		{
			delete n;
			n=nule;
		}
		else if(n->l != nule && n->r !=nule)
		{
			if(n->l->priority > n->r->priority) L(n);
			else R(n);
			erase(n,val);
		}
		else
		{
			if(n->l != nule) L(n);
			else R(n);
			erase(n,val);
		}
	}
	balance(n);
}

int main()
{
	srand(time(NULL));
	nule=new node(NULL,NULL,0,0,0,0,0);
	rad=nule;
	char s;
	int x;
	while(s!=EOF)
	{
		s=in.get();
		if(s=='I')
		{
			in>>x;
			if(!search(rad,x))
				insert(rad,x,rand()%666013 +1);
		}
		if(s=='S')
		{
			in>>x;
			if(search(rad,x))
				erase(rad,x);
			else out<<"-1"<<"\n";
		}
		if(s=='C')
		{
			in>>x;
			out<<search(rad,x)<<"\n";
		}
		if(s=='M')
		{
			s=in.get();
			if(s=='A')
				out<<maxdif(rad)<<"\n";
			else
				out<<mindif(rad)<<"\n";
			in.get();
		}
		in.get();
	}
	return 0;
}