#include <bits/stdc++.h>

using namespace std;

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


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

	node(node *l,node *r,int val,int priority,int minn,int mxx,int minndif){
		this->l=l;
		this->r=r;
		key=val;
		priority=priority;
		minn=minn;
		mxx=mxx;
		minndif=minndif;
	}
} *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->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)
			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);
	}
}

void dfs(node *&n)
{
	if(n==nule) return;
	out<<n->key<<" "<<n->priority<<"\n";
	dfs(n->l);
	dfs(n->r);
}
int main()
{
	rad=nule=new node(NULL,NULL,0,0,0,0,0);
	char s;
	int x;
	while(s!=EOF)
	{
		s=in.get();
		if(s=='I')
		{
			in>>x;
			if(!search(rad,x))
				insert(rad,x,rand()%MOD +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;
}