#include <iostream>
#include <fstream>
#include <string>
#include <queue>
#include <cmath>

std::ifstream f("zeap.in");
std::ofstream g("zeap.out");

const int infinit = 1e9 + 1;

struct nod
{
	int key;
	int priority;
	nod* left;
	nod* right;

	nod();
	nod(int cheie, int prioritate, nod* stang, nod* drept)
	{
		key = cheie;
		priority = prioritate;
		left = stang;
		right = drept;
	}
	nod* operator = (nod* sursa)
	{
		key = sursa->key;
		priority = sursa->priority;
		left = sursa->left;
		right = sursa->right;
		return this;
	}
	//void afisare()
	//{
	//	std::cout << "  { " << key << " : " << priority << " }";
	//}
};
nod * nodgol = new nod(-infinit, -infinit, NULL, NULL);
nod* R = new nod(-infinit, -infinit, nodgol, nodgol);

nod::nod()
{
	left = nodgol;
	right = nodgol;
	key = -404;
	priority = -404;
}

struct distanta
{
	nod* predecesor;
	nod* succesor;
	int dist;

	void actualizeaza_dist()
	{
		dist = succesor->key - predecesor->key;
	}
	distanta(nod* p, nod* s)
	{
		predecesor = p;
		succesor = s;
		dist = succesor->key - predecesor->key;
	}
};

struct cmp_for_distantele
{
	bool operator() (distanta& a, distanta& b)
	{
		return a.dist > b.dist;		//  distantele = pq, deci va tine in radacina distanta cu .dist minim
	}
};
std::priority_queue <distanta, std::vector<distanta>, cmp_for_distantele> distantele, aux;   //  aux este pt cand editam o distanta

bool cauta(nod* crt, int cheie_cautata)
{
	if (crt == nodgol)
		return 0;

	if (cheie_cautata == crt->key)
		return 1;
	if (cheie_cautata < crt->key)
		return cauta(crt->left, cheie_cautata);
	return cauta(crt->right, cheie_cautata);
}

void rotire_st(nod*& crt)
{
	nod* stangul = crt->left;
	crt->left = stangul->right;
	stangul->right = crt;
	crt = stangul;
}

void rotire_dr(nod*& crt)
{
	nod* dreptul = crt->right;
	crt->right = dreptul->left;
	dreptul->left = crt;
	crt = dreptul;
}

void balans(nod*& crt)
{
	if (crt->left->priority > crt->priority)
		rotire_st(crt);
	else if (crt->right->priority > crt->priority)
		rotire_dr(crt);
}

bool dublat = false;
void inserare(nod*& crt, int cheie, int prioritate, nod*& noul)
{
	if (crt == nodgol)
	{
		crt = new nod(cheie, prioritate, nodgol, nodgol);
		noul = crt;
		return;
	}
	if (cheie < crt->key)
		inserare(crt->left, cheie, prioritate, noul);
	else if (cheie > crt->key)
		inserare(crt->right, cheie, prioritate, noul);
	else if (cheie == crt->key)
		dublat = true;

	if(dublat == false)
		balans(crt);
}

void succesor(nod* crt, int cheie, char poz_relativa, nod*& result, int& countdown)		// apelarea:   nod = R | cheie = ce cautam | poz_relativa = 'x' (sa nu fie s sau d)
{																																			//                  result = -1 |  countdown = 3
	if (countdown == 3)		//   coboram sa cautam cheia 
	{
		if (crt->key != cheie)
		{
			if (crt->left != nodgol and cheie < crt->key)
			{
				poz_relativa = 's';
				succesor(crt->left, cheie, poz_relativa, result, countdown);
			}
			else if (cheie < crt->key)   // nu putem gasi numarul, dar crt este succesorul
			{
				countdown = 0;
				result = crt;
			}
			else if (crt->right != nodgol and crt->key < cheie)
			{
				poz_relativa = 'd';
				succesor(crt->right, cheie, poz_relativa, result, countdown);
			}
			else   // nu putem gasi numarul, nici succesorul
			{
				// result ramane nodgol;
				return;
			}

			if (countdown == 2 and poz_relativa == 's')       // urcam inapoi sa luam primul nod care a coborat pe fiul stang
			{
				countdown = 0;
				result = crt;
			}
		}
		else if (crt->right != nodgol)	  //  daca exista subarborele drept, continuam cautarea acolo; 
		{
			countdown = 1;
			succesor(crt->right, cheie, poz_relativa, result, countdown);
		}
		else                                       //  daca nu exista subarborele drept, ne intoarcem din functiile recursive
			countdown = 2;
	}
	else if (countdown == 1)      // dupa ce am gasit cheia, cautam cel mai stang nod din subarborele drept
	{
		if (crt->left == nodgol)   // gata, am gasit succesorul
		{
			countdown = 0;
			result = crt;
		}
		else
			succesor(crt->left, cheie, poz_relativa, result, countdown);
	}
}
void predecesor(nod* crt, int cheie, char poz_relativa, nod*& result, int& countdown)   // apelarea:   nod = R | cheie = ce cautam | poz_relativa = 'x' (sa nu fie s sau d)
{																																			  //                  result = -1 |  countdown = 3
	if (countdown == 3)		//   coboram sa cautam cheia
	{
		if (crt->key != cheie)
		{
			if (crt->left != nodgol and cheie < crt->key)
			{
				poz_relativa = 's';
				predecesor(crt->left, cheie, poz_relativa, result, countdown);
			}
			else if (cheie < crt->key)		//  nu putem gasi numarul, nici predecesorul
			{
				// result ramane nodgol
				return;
			}
			else if (crt->right != nodgol and crt->key < cheie)
			{
				poz_relativa = 'd';
				predecesor(crt->right, cheie, poz_relativa, result, countdown);
			}
			else    // nu putem gasi numarul, dar crt este predecesorul
			{
				countdown = 0;
				result = crt;
			}

			if (countdown == 2 and poz_relativa == 'd')       // urcam inapoi sa luam primul nod care a coborat pe fiul drept
			{
				countdown = 0;
				result = crt;
			}
		}
		else if (crt->left != nodgol)	  //  daca exista subarborele stang, continuam cautarea acolo; 
		{
			countdown = 1;
			predecesor(crt->left, cheie, poz_relativa, result, countdown);
		}
		else                                       //  daca nu exista subarborele stang, ne intoarcem din functiile recursive
			countdown = 2;
	}
	else if (countdown == 1)	   // dupa ce am gasit cheia, cautam cel mai drept nod din subarborele stang
	{
		if (crt->right == nodgol)  // gata, am gasit predecesorul
		{
			countdown = 0;
			result = crt;
		}
		else
			predecesor(crt->right, cheie, poz_relativa, result, countdown);
	}
}

int stergere(nod*& crt, int cheie)
{
	if (crt == nodgol)
		return -1;

	if (cheie < crt->key)
		return stergere(crt->left, cheie);
	else if (cheie > crt->key)
		return stergere(crt->right, cheie);
	else
	{
		if (crt->left == nodgol and crt->right == nodgol)
		{
			nod* succesor_vechi = nodgol;
			int countdown = 3;
			succesor(R, crt->key, 'x', succesor_vechi, countdown);

			nod* predecesor_vechi = nodgol;
			countdown = 3;
			predecesor(R, crt->key, 'x', predecesor_vechi, countdown);

			bool pOk = false,  crtOk = false;
			if (predecesor_vechi == nodgol)
				pOk = true;
			while (!pOk or !crtOk)
			{
				if (distantele.top().predecesor->key == predecesor_vechi->key)
				{
					if (succesor_vechi != nodgol)    // legam predecesor de succesor
					{
						distanta deActualizat = distantele.top();
						deActualizat.succesor = succesor_vechi;
						deActualizat.actualizeaza_dist();
						aux.push(deActualizat);
					}
					distantele.pop();
					pOk = true;
				}
				else if (distantele.top().predecesor->key == crt->key)
				{
					distantele.pop();
					crtOk = true;
				}
				else
				{
					aux.push(distantele.top());
					distantele.pop();
				}
			}
			while (!aux.empty())
			{
				distantele.push(aux.top());
				aux.pop();
			}

			delete crt;
			crt = nodgol;
			return 1;
		}

		else if (crt->left->priority > crt->right->priority)
			rotire_st(crt);
		else
			rotire_dr(crt);
		return stergere(crt, cheie);
	}
}

//const int infinit = 1e9+1;
//void split(nod*& root, nod*& root_left, nod*& root_right, int cheie)
//{
//	inserare(root, cheie, infinit);
//	root_left = root->left;
//	root_right = root->right;
//	delete root;
//	root = nodgol;
//}
//void join(nod*& root, nod*& root_left, nod*& root_right, int cheie)
//{
//	root = new nod(cheie, 0, root_left, root_right);
//	stergere(root, root->key);
//}
//void afis_elem_sortate(nod* crt)
//{
//	if (crt == NULL)
//		return;
//	if (crt->left != nodgol)
//		afis_elem_sortate(crt->left);
//	crt->afisare();
//	if (crt->right != nodgol)
//		afis_elem_sortate(crt->right);
//}

int cautaMaximul(nod* crt)
{
	if (crt->right != nodgol)
		return cautaMaximul(crt->right);

	return crt->key;
}

int cautaMinimul(nod* crt)
{
	if (crt->left != nodgol)
		return cautaMinimul(crt->left);

	return crt->key;
}

int main()
{
	srand(time(NULL));

	std::string comanda;
	int  x,  prioritate,   minim = infinit,   maxim = -infinit,  nrNoduri = 0;
	bool stimMinimul = true, stimMaximul = true;
	while (f>>comanda)
	{
		if (comanda[0] == 'I')				// insereaza x
		{
			f >> x;
			prioritate = rand() % 15000 + 1;
			
			if (stimMinimul and minim > x)
				minim = x;
			if (stimMaximul and maxim < x)
				maxim = x;

			nod* succesor_nou = nodgol;
			int countdown = 3;
			succesor(R, x, 'x', succesor_nou, countdown);

			nod* predecesor_nou = nodgol;
			countdown = 3;
			predecesor(R, x, 'x', predecesor_nou, countdown);

			nod* noul = nodgol;
			dublat = false;
			inserare(R, x, prioritate, noul);
			if (dublat == false)	// am reusit sa iunseram nodul nou
			{
				nrNoduri++;
				if (predecesor_nou!= nodgol and succesor_nou != nodgol)
				{
					distanta distNoua(noul, succesor_nou);

					int keye = predecesor_nou->key;
					while (distantele.top().predecesor->key != keye)		// cautam distanta aspciata predecesorului
					{                                                                               // mutand din distantele in aux
						aux.push(distantele.top());
						distantele.pop();
					}
					distanta predToNew = distantele.top();	// modificam distanta de la predecesor la nodul nou
					distantele.pop();
					predToNew.succesor = noul;
					predToNew.actualizeaza_dist();
					distantele.push(predToNew);

					while (!aux.empty())                 // aducaem inapoi in distantele ce am pus in aux
					{
						distantele.push(aux.top());
						aux.pop();
					}

					distantele.push(distNoua);      // in fine, inseram si distanta noua
				}
				else if (predecesor_nou != nodgol)    
				{
					distanta distNoua(predecesor_nou, noul);
					distantele.push(distNoua);
				}
				else          // care e totuna cu: else if (succesor_nou != nodgol)
				{
					distanta distNoua(noul, succesor_nou);
					distantele.push(distNoua);
				}
			}
				
		}
		else if (comanda[0] == 'S')		// sterge x
		{
			f >> x;
			if (minim == x)
			{
				minim = infinit;
				stimMinimul = false;
			}
			if (maxim == x)
			{
				maxim = -infinit;
				stimMaximul = false;
			}

			int sters = stergere(R, x);
			if (sters == -1)
				g << "-1\n";
			else
				nrNoduri--;
		}
		else if (comanda[0] == 'C')		// cauta x
		{
			f >> x;
			g << cauta(R, x) << "\n";
		}
		else if (comanda[1] == 'A')		// max-dif
		{
			if (nrNoduri >= 2)
			{
				if ( !stimMaximul)
				{
					maxim = cautaMaximul(R);
					stimMaximul = true;
				}
				
				if (!stimMinimul)
				{
					minim = cautaMinimul(R);
					stimMinimul = true;
				}

				g << maxim - minim << "\n";
			}
			else
				g << "-1\n";
		}
		else											// min-dif
		{
			if (!distantele.empty())
				g << distantele.top().dist << "\n";
			else
				g << "-1\n";
		}
	}

	return 0;
}