#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <algorithm>
using namespace std;

const int dim = 100002, OO = (1<<31)-1;
int N;
struct trp {
	trp *st, *dr;
	int ch, pr, df, es, ed;
} *R;


void init (trp* &n, int cheie, int prior)
{
	n = new trp;
	n->ch = n->es = n->ed = cheie;
	n->pr = prior;
	n->st = n->dr = NULL;
	n->df = OO;
}

void difmin (trp* &n)
{
	int m1, m2;

	if (n->st != NULL)
	{
		n->es = n->st->es;
		m1 = min (n->st->df, abs (n->ch - n->st->ed));
	}
	else
		n->es = n->ch;

	if (n->dr != NULL)
	{
		n->ed = n->dr->ed;
		m2 = min (n->dr->df, abs (n->ch - n->dr->es));
	}
	else
		n->ed = n->ch;

	n->df = min (m1, m2);
}

void rot_st (trp* &n)
{
	trp* aux = n->st;
	n->st = aux->dr;
	aux->dr = n;
	n = aux;
}	

void rot_dr (trp* &n)
{
	trp* aux = n->dr;
	n->dr = aux->st;
	aux->st = n;
	n = aux;
}

void balance (trp* &n)
{
	if (n->st != NULL)
		if (n->pr < n->st->pr)
			rot_st (n);
	if (n->dr != NULL)
		if (n->pr < n->dr->pr)
			rot_dr (n);	
}

void insert (trp* &n, int cheie, int prior)
{
	if (n == NULL)
	{
		init (n, cheie, prior);
		return;
	}
	
	if (cheie == n->ch)
		return;
	
	if (cheie < n->ch)
		insert (n->st, cheie, prior);
	else
		insert (n->dr, cheie, prior);
	
	balance (n);
	difmin (n);
}

void deleta (trp* &n, int cheie)
{
	if (n->ch != cheie)
	{
		if (n->st != NULL && cheie < n->ch)
			deleta (n->st, cheie);
		else if (n->dr != NULL)
			deleta (n->dr, cheie);
	}
	else
	{
		if (n->st == NULL && n->dr == NULL)
		{
			delete n;
			n = NULL;
			return;
		}
		else
		{
			if (n->st == NULL)
				rot_dr (n);
			else if (n->dr == NULL)
				rot_st (n);
			else if (n->st->pr > n->dr->pr)
				rot_st (n);
			else
				rot_dr (n);
			deleta (n, cheie);
		}
	}
	difmin (n);	
}

int cauta (trp* n, int cheie)
{
	if (n == NULL)
		return 0;
	if (n->ch == cheie)
		return 1;
	
	if (cheie < n->ch)
		return cauta (n->st, cheie);
	else
		return cauta (n->dr, cheie);
}

int cautamax (trp* n)
{
	trp *q, *r;
	for (q = n; q->st != NULL; q = q->st);
	for (r = n; r->dr != NULL; r = r->dr);
	return abs (r->ch - q->ch);
}

int verif (trp* n)
{
	int ok = 1;
	if (n->st != NULL)
	{
		ok = n->ch >= n->st->ch && n->pr >= n->st->pr;
		ok = ok && verif (n->st);
	}
	if (n->dr != NULL)
	{
		ok = n->ch <= n->dr->ch && n->pr >= n->dr->pr;
		ok = ok && verif (n->dr);
	}
	return ok;	
}

void parsare (char s[], int &val)
{
	int i = 0; val = 0;
	while (!('0' <= s[i] && s[i] <= '9')) i++;
	while ('0' <= s[i] && s[i] <= '9') val = val * 10 + s[i++] - '0';
}

void cit ()
{
	char S[10];
	int cheie, prior;
	R = NULL;
	while ( fgets (S, 10, stdin) > 0 )
	{
		parsare (S, cheie);
		switch (S[0])
		{
			case 'I':
				prior = rand () * rand ();
				insert (R, cheie, prior);
				break;
			case 'S':
				if (!cauta (R, cheie))
					printf ("-1\n");
				else
					deleta (R, cheie);
				break;
			case 'C':
				if (cauta (R, cheie))
					printf ("1\n");
				else
					printf ("0\n");
				break;
			case 'M':
				if (R == NULL)
				{
					printf ("-1\n");
					break;
				}				
				if (R->st == NULL && R->dr == NULL)
				{
					printf ("-1\n");
					break;
				}
				
				if (S[1] == 'A')
					printf ("%d\n", R->ed - R->es);
				else
					printf ("%d\n", R->df);
				break;
		}
	}
}

int main ()
{
	freopen ("zeap.in", "r", stdin);
	freopen ("zeap.out", "w", stdout);
	
	srand ( time(NULL) );
	cit ();	
	return 0;	
}