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

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

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 << " }";
	//}
} *R, * nodgol;

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

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)
{
	if (crt == nodgol)
	{
		crt = new nod(cheie, prioritate, nodgol, nodgol);
		return;
	}
	if (cheie < crt->key)
		inserare(crt->left, cheie, prioritate);
	else if (cheie > crt->key)
		inserare(crt->right, cheie, prioritate);
	else if (cheie == crt->key)
		dublat = true;

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

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)
		{
			delete crt;
			crt = nodgol;
			return 1;
		}

		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);
//}
//void succesor(const nod* crt, int cheie, char poz_relativa, int& result, int& countdown)
//{
//	if (countdown == 2)		//   coboram sa cautam cheia / urcam inapoi sa luam primul nod care a coborat pe fiul stang
//	{
//		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 (crt->right != nodgol and crt->key < cheie)
//			{
//				poz_relativa = 'd';
//				succesor(crt->right, cheie, poz_relativa, result, countdown);
//			}
//
//			if (countdown == 2 and poz_relativa == 's')
//			{
//				countdown = 0;
//				result = crt->key;
//			}
//		}
//		else if (crt->right != nodgol)	  //  daca exista subarborele drept, continuam cautarea acolo; 
//		{											  //  daca nu, ne intoarcem din functiile recursive
//			countdown = 1;
//			succesor(crt->right, cheie, poz_relativa, result, countdown);
//		}
//	}
//	else if (countdown == 1)	// dupa ce am gasit cheia, cautam cel mai stang nod din subarborele drept
//	{
//		if (crt->left == nodgol)
//		{
//			countdown = 0;
//			result = crt->key;
//		}
//		else
//			succesor(crt->left, cheie, poz_relativa, result, countdown);
//	}
//}
//void predecesor(const nod* crt, int cheie, char poz_relativa, int& result, int& countdown)
//{
//	if (countdown == 2)		//   coboram sa cautam cheia / urcam inapoi sa luam primul nod care a coborat pe fiul drept
//	{
//		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 (crt->right != nodgol and crt->key < cheie)
//			{
//				poz_relativa = 'd';
//				predecesor(crt->right, cheie, poz_relativa, result, countdown);
//			}
//
//			if (countdown == 2 and poz_relativa == 'd')
//			{
//				countdown = 0;
//				result = crt->key;
//			}
//		}
//		else if (crt->left != nodgol)	  //  daca exista subarborele stang, continuam cautarea acolo; 
//		{											  //  daca nu, ne intoarcem din functiile recursive
//			countdown = 1;
//			predecesor(crt->left, cheie, poz_relativa, result, countdown);
//		}
//	}
//	else if (countdown == 1)	// dupa ce am gasit cheia, cautam cel mai drept nod din subarborele stang
//	{
//		if (crt->right == nodgol)
//		{
//			countdown = 0;
//			result = crt->key;
//		}
//		else
//			predecesor(crt->right, cheie, poz_relativa, result, countdown);
//	}
//}

void diferentaMinima(nod* crt, int& difmin)
{
	if (crt->left != nodgol)
	{
		if (difmin > fabs(crt->key - crt->left->key))
			difmin = fabs(crt->key - crt->left->key);
	}
	if (crt->right != nodgol)
	{
		if (difmin > fabs(crt->key - crt->right->key))
			difmin = fabs(crt->key - crt->right->key);
	}
}

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()
{
	R = nodgol = new nod(0, 0, NULL, NULL);
	srand(time(NULL));

	std::string comanda;
	const int infinit = 1e9 + 1;
	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;

			dublat = false;
			inserare(R, x, prioritate);
			if (dublat == false)
				nrNoduri++;
		}
		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 (nrNoduri >= 2)
			{
				int difmin = infinit;
				diferentaMinima(R, difmin);
				g << difmin << "\n";
			}
			else
				g << "-1\n";
		}
	}

	return 0;
}