/***
 *** Patrick Sava
 *** University of Bucharest
 ***/

#include <fstream>
#include <ctime>
#include <cstdlib>

using namespace std ;

#define FORN(a,b,c) for(int a=b;a<=c;++a)
#define FORNBACK(a,b,c) for(int a=b;a>=c;--a)
#define mp make_pair
#define pb push_back

ifstream cin ("zeap.in") ;
ofstream cout ("zeap.out") ;

class Treap {


	public :
	struct Tr {

		Tr *st ;
		Tr *dr ;
		int priority ;
		int value ;
		int minim ;
		int maxim ;
		int mindif ;

		Tr ( Tr *leftson , Tr *rightson , int setpriority , int setvalue , int setminim , int setmaxim, int setmindif )
		{
			this -> st = leftson ;
			this -> dr = rightson ;
			this -> priority = setpriority ;
			this -> value = setvalue ;
			this -> minim = setminim ;
			this -> maxim = setmaxim ;
			this -> mindif = setmindif ;
		}
	} ;

	Tr *Root, *Nil ;

	Treap ()
	{
		srand ( time ( NULL ) ) ;
		Root = Nil = new Tr ( NULL , NULL , 0 , 0 , 0 , 0 ,0 ) ;
	}

	void Insert ( int value ) {
		if ( Find (value) == false ) {
			Insert (Root, value, rand() % 666013 + 1) ;
		}
	}

	void Erase ( int value ) {
		if ( Find (value) == true ) {
			Erase (Root, value) ;
			return ;
		}
		cout << -1 << '\n' ;
	}

	bool Find ( int value ) {
		return Find ( Root, value ) ;
	}

	int MaxDiff () {
		if ( Root -> maxim != Root -> minim )
			return Root -> maxim - Root -> minim ;
		return -1 ;
	}

	int MinDiff () {
		if ( Root -> mindif and Root -> mindif != int(2e9) + 1) {
			return Root -> mindif ;
		}
		return -1 ;
	}

	void Debug ( Tr *Node ) {
		if ( Node == Nil ) {
			return ;
		}
		Balance (Node);
		Debug ( Node -> st ) ;
		cout << Node -> value << '\n' ;
		Debug ( Node -> dr ) ;
	}

	private :
	void RotateLeft ( Tr *&Node ) {
		Recheck ( Node ) ;
		Tr *Aux = Node -> st ;
		Node -> st = Aux -> dr ;
		Aux -> dr = Node ;
		Node = Aux ;
		Recheck ( Node -> st ) ;
		Recheck ( Node -> dr ) ;
		Recheck ( Node ) ;
	}

	void RotateRight ( Tr *&Node ) {
		Recheck ( Node ) ;
		Tr *Aux = Node -> dr ;
		Node -> dr = Aux -> st ;
		Aux -> st = Node ;
		Node = Aux ;
		Recheck ( Node -> st ) ;
		Recheck ( Node -> dr ) ;
		Recheck ( Node ) ;
	}

	void Balance ( Tr *&Node ) {
		Recheck (Node) ;
		if ( Node != Nil and Node -> priority < Node -> st -> priority ) {
			RotateLeft (Node) ;
		}
		else if ( Node != Nil and Node -> priority < Node -> dr -> priority ) {
			RotateRight (Node) ;
		}
	}

	void Recheck ( Tr *&Node ) {
		/// value , minim, maxim, mindiff
		if ( Node == Nil ) {
			return ;
		}
		Node -> mindif = int(2e9) + 1 ;
		Node -> minim = Node -> value ;
		Node -> maxim = Node -> value ;
		if ( Node -> st != Nil ) {
			Node -> minim = min ( Node -> minim , Node -> st -> minim ) ;
			Node -> maxim = max ( Node -> maxim , Node -> st -> maxim ) ;
			Node -> mindif = min ( Node -> mindif , Node -> value - Node -> st -> value ) ;
			Node -> mindif = min ( Node -> mindif , Node -> value - Node -> st -> maxim ) ;
			Node -> mindif = min ( Node -> mindif , Node -> st -> mindif ) ;
		}
		if ( Node -> dr != Nil ) {
			Node -> minim = min ( Node -> minim , Node -> dr -> minim ) ;
			Node -> maxim = max ( Node -> maxim , Node -> dr -> maxim ) ;
			Node -> mindif = min ( Node -> mindif , Node -> dr -> value - Node -> value ) ;
			Node -> mindif = min ( Node -> mindif , Node -> dr -> minim - Node -> value ) ;
			Node -> mindif = min ( Node -> mindif , Node -> dr -> mindif ) ;
		}
 	}

	bool Find ( Tr *&Node , int value ) {
		if ( Node == Nil ) {
			return false ;
		}
		if ( Node -> value == value ) {
			return true ;
		}
		if ( Node -> value < value ) {
			return Find ( Node -> dr , value ) ;
		}
		return Find ( Node -> st , value ) ;
	}

	void Insert ( Tr *&Node , int value , int priority ) {
		if ( Node == Nil ) {
			Node = new Tr ( Nil , Nil , priority , value , value, value, int(2e9) + 1 ) ;
			return ;
		}
		if ( Node -> value < value ) {
			Insert ( Node -> dr , value , priority ) ;
		}
		else if ( Node -> value > value ) {
			Insert ( Node -> st , value , priority ) ;
		}
		Balance ( Node ) ;
	}

	void Erase ( Tr *&Node , int value ) {
		if ( Node == Nil ) {
			return ;
		}

		if ( Node -> value > value ) {
			Erase ( Node -> st , value ) ;
		}
		else if ( Node -> value < value ) {
			Erase ( Node -> dr , value ) ;
		}
		else {
			if ( Node -> dr == Nil and Node -> st == Nil ) {
				delete Node ;
				Node = Nil ;
			}
			else {
				if ( Node -> st -> priority > Node -> dr -> priority ) {
					RotateLeft ( Node ) ;
				}
				else {
					RotateRight ( Node ) ;
				}
				Erase ( Node , value ) ;
			}
		}
		Balance (Node) ;
	}
};

Treap *T = new Treap() ;

int main ()
{
	string Op ;
	while ( cin >> Op ) {
		//cout << "Am afisat : " ;
		if ( Op == "I" ) {
			int x ;
			cin >> x ;
			//cout << x << endl ;
			T->Insert (x) ;
		}
		else if ( Op == "S" ) {
			int x ;
			cin >> x ;
			T->Erase (x) ;
		}
		else if ( Op == "C" ) {
			int x ;
			cin >> x ;
			cout << T->Find(x) << '\n' ;
		}
		else if ( Op == "MAX" ) {
			cout << T->MaxDiff () << '\n' ;
		}
		else {
			cout << T->MinDiff () << '\n' ;
		}
		//cout << "Maximul este " << T->Root->maxim << '\n' ;
		//cout << "Minimul este " << T->Root->minim << '\n' ;
		//cout << "--------------------------------------\n";
		/*cout << "\n\n\n" ;
		T -> Debug (T->Root) ;
		cout << "--------------------------------------\n";*/
	}
	return 0 ;
}