#include <fstream>
#include <string>
#include <iostream>

using namespace std;

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

const int val = (1 << 15) - 1;

int RandomNumber() {

	return ((rand() & val) << 15)  + (rand() & val);
}

struct Treap{

	Treap *l , *r;
	Treap *cum;
	int key,pr,mi,ma,difmin,cnt;
	Treap(Treap *L,Treap *R,int _key,Treap *_cum) {
		l = L;
		r = R;
		cum = _cum;
		mi = ma = _key;
		difmin = 0x3f3f3f3f;
		key = _key;
		cnt = 1;
		pr = RandomNumber();
	}
	Treap() {
		l = nullptr;
		r = nullptr;
		cum = nullptr;
		key = pr = 0;
		cnt = 0;
		mi = 0x3f3f3f3f;
		ma = -0x3f3f3f3f;
		difmin = 0x3f3f3f3f;
	}
} *noo = new Treap();

void refresh(Treap *&t) {

	t->difmin = 0x3f3f3f3f;
	t->mi = t->key;
	t->ma = t->key;
	if ( t->r != noo)
		t->cnt += t->r->cnt;
	if ( t-> l != noo)
		t->cnt += t->l->cnt;
	if ( t->l != noo)
	t->mi = min(t->l->mi,t->key);
	if ( t->r != noo)
	t->ma = max(t->r->ma,t->key);
	if ( t->cnt < 2 )
		return;
	if ( t->l != noo) {
	t->difmin = t->key - t->l->ma;
	t->difmin = min(t->l->difmin,t->difmin);
	}
	if ( t->r != noo) {

	t->difmin = min(t->r->mi - t->key,t->difmin);
	t->difmin = min(t->r->difmin,t->difmin);
	}
}
void refreshT(Treap *&t) {

	t->difmin = 0x3f3f3f3f;
	t->mi = 0x3f3f3f3f;
	t->ma = 0;
	t->cnt = 0;
	if ( t->r != noo)
		t->cnt += t->r->cnt;
	if ( t-> l != noo)
		t->cnt += t->l->cnt;
	if ( t->l != noo)
	t->mi = t->l->mi;
	if ( t->r != noo)
	t->ma = t->r->ma;
	if ( t->cnt < 2 )
		return;
	if ( t->l != noo) {
	t->difmin = t->l->difmin;
	}
	if ( t->r != noo) {


	t->difmin = min(t->r->difmin,t->difmin);
	}
	//cout << t->difmin << "\n";
}


void rotate_left(Treap *&t)
{
    Treap *aux = t->l;
    t->l = aux->r;
    aux->r = t;
    t = aux;

     refresh(t->r); refresh(t);
}

void rotate_right(Treap *&t)
{
    Treap *aux = t->r;
    t->r = aux->l;
    aux->l = t;
    t = aux;

    refresh(t->l); refresh(t);
}

void balance(Treap *&t)
{
	if ( t == noo)
		return;
    if(t->l->pr> t->pr) rotate_left(t);
        else if(t->r->pr > t->pr) rotate_right(t);

}

void Pr(Treap *&t) {

	if ( t == noo)
		return;
	if ( t-> l != noo)
		Pr(t->l);
	cout << t->key << " ";
	if ( t-> r != noo)
		Pr(t->r);

}

void Insert(Treap *&t, int value,Treap*&wh){

	if ( t == noo) {
		t = new Treap(noo,noo,value,wh);
		t->cum = wh;
		balance(t);
		refresh(t);
		return;
	}
	if ( t->key > value) Insert(t->l,value,t);
	else
		if ( t->key < value )Insert(t->r,value,t);
	refresh(t);
	balance(t);

}bool ok = true;

bool use = false;

void Exi(Treap *t) {
	if (t->cum == nullptr)
        return;
	cout << t->key << " "<<t->difmin << "\n";
	refresh(t);
	if( t->cum != noo)
	Exi(t->cum);


}
bool used = 0;
void Erase(Treap *&t, int value) {

	if ( t == noo)
		return;
	if ( value < t->key)
		Erase(t->l,value);
	else if ( value > t->key )
			Erase(t->r,value);
	else
		{

			if ( t -> l == noo and t->r == noo) {



				t = noo, delete t;
			}
			else
				if ( t->l->pr > t->r->pr) rotate_left(t);
				else
					rotate_right(t);

			Erase(t,value);

			ok = true;
		}
}


void Search(Treap *&t, int value) {

	if ( t == noo)
		return ;
	if ( value > t->key)
		Search(t->r,value);
	else
		if ( value < t->key)
			Search(t->l,value);
	else
		ok = true;
}


char S[20];

int main() {

	int x;
	srand(time(0));
	Treap *t;
	t = noo;
	while ( fin >> (S+1)) {
		if ( S[1] == 'I') {
			fin >> x;
			Insert(t,x,noo);

		}
		else if ( S[1] == 'S') {
			fin >> x;
			ok = false;
			used = 0;
			Erase(t,x);
			if ( ok == false)
				fout << -1 << "\n";
		}
		else if ( S[1] == 'C') {
			fin >> x;
			ok = false;
			Search(t,x);
				fout << ok << "\n";
		}
		else if ( S[1] == 'M' and S[2] == 'A') {
					fout << t->ma - t->mi << "\n";
		}
		else {
			fout << t->difmin << "\n";
		}
	}
}