#include <stdlib.h>
#include <fstream>
#include <iostream>
#include <string>
#include <queue>
#include <stack>
#include <vector>
#include <string.h>
#include <iomanip>
#include <time.h>
using namespace std;


const string file = "zeap";

const string infile = file + ".in";
const string outfile = file + ".out";


struct Nod
{
	int v;

	int h;
	int min;
	int max;

	int mindif;
	int maxdif;

	Nod* l;
	Nod* r;
};

Nod *T, *NIL;
int tSize = 0;

void initTree()
{
	NIL = new Nod();
	NIL->l = NIL;
	NIL->r = NIL;
	NIL->h = 0;
	NIL->v = 0;
	NIL->min = 0x3f3f3f3f;
	NIL->max = - 0x3f3f3f3f;
	NIL->maxdif = - 0x3f3f3f3f;
	NIL->mindif = 0x3f3f3f3f;
	T = NIL;
}


inline void updateNod(Nod* nod)
{
	nod->h = max(nod->l->h, nod->r->h) + 1;
	nod->min = min(nod->l->min, nod->v);
	nod->max = max(nod->r->max, nod->v);

	nod->maxdif = nod->max - nod->min;
	nod->mindif = min(nod->l->mindif, nod->r->mindif);
	nod->mindif = min(nod->mindif, nod->r->min - nod->l->max);
	nod->mindif = min(nod->mindif, nod->r->min - nod->v);
	nod->mindif = min(nod->mindif, nod->v - nod->l->max);
}

Nod* rotl(Nod* n)
{
	Nod* t = n->r;

	n->r = t->l;
	t->l = n;
	
	updateNod(n);
	updateNod(t);

	return t;
}

Nod* rotr(Nod* n)
{
	Nod * t = n->l;
	n->l = t->r;
	t->r = n;

	updateNod(n);
	updateNod(t);

	return t;
}

Nod* balance(Nod* n)
{
	updateNod(n);

	if(n->l->h > n->r->h + 1)
	{
		if(n->l->r->h > n->l->l->h)
		{
			n->l = rotl(n->l);
		}

		n = rotr(n);
	}
	else if(n->r->h > n->l->h + 1)
	{
		if(n->r->l->h > n->r->r->h)
		{
			n->r = rotr(n->r);
		}
		n = rotl(n);
	}

	return n;
}

Nod* insert(Nod* n, int v)
{
	if(n == NIL)
	{
		Nod* t = new Nod();
		t->h = 0;
		t->l = NIL;
		t->r = NIL;
		t->max = v;
		t->min = v;
		t->maxdif = 0;
		t->mindif = 0x3f3f3f3f;
		t->v = v;
		tSize ++;
		return t;
	}

	if( v < n->v)
	{
		n->l = insert(n->l, v);
	}
	else if(v > n->v)
	{
		n->r = insert(n->r, v);
	}
	return balance(n);
}

Nod* remove(Nod* n, int v)
{
	if(n == NIL)
	{
		return NIL;
	}

	if(n->v == v)
	{
		if(n->l == NIL || n->r == NIL)
		{
			Nod* t;
			t = n->l == NIL ? n->r : n->l;
			delete(n);
			tSize --;
			return t;
		}
		else
		{
			Nod * t;
			for(t = n->r; t->l != NIL; t = t->l);
			n->v = t->v;
			n->r = remove(n->r, t->v);
		}
	}
	else if(v < n->v)
	{
		n->l = remove(n->l, v);
	}
	else if(v > n->v)
	{
		n->r = remove(n->r, v);
	}
	return balance(n);
}

bool search(Nod* n, int v)
{
	if(n == NIL)
	{
		return false;
	}
	
	if(n->v == v)
	{
		return true;
	}

	if(v < n->v)
	{
		return search(n->l, v);
	}
	else if(v > n->v)
	{
		return search(n->r, v);
	}
	return false;
}



void citire()
{
	ifstream fin(infile.c_str());
	ofstream fout(outfile.c_str());

	char sir[30];

	while(fin.getline(sir, 30))
	{
		int nr;
		int s;
		char * p;
		switch(sir[0])
		{
		case 'I':
			nr = 0;
			p = strchr(sir, ' ');
			nr = atoi(p + 1);
			T = insert(T, nr);
			break;
		case 'S':
			nr = 0;
			p = strchr(sir, ' ');
			nr = atoi(p + 1);
			s = tSize;
			T = remove(T, nr);
			if(s == tSize)
			{
				fout << "-1\n";
			}
			break;
		case 'C':
			nr = 0;
			p = strchr(sir, ' ');
			nr = atoi(p + 1);
			fout << search(T, nr) << "\n";
			break;
		case 'M':
			if(tSize < 2)
			{
				fout << -1 << "\n";
			}

			if(sir[1] == 'A')
			{
				fout << T->maxdif << "\n";
			}
			else
			{
				fout << T->mindif << "\n";
			}
			break;
		}
	}


	fout.close();
	fin.close();
}



int main()
{
	initTree();
	citire();


}