#include <iostream>
#include <fstream>
#include <vector>
#include <string>
using namespace std;
#define INT_MAX 2147483647;

//very S O L I D 100%
class BST{
	int data;
	BST* left, * right;

public:
	BST();
	BST(int);
	BST* Insert(BST*, int);
	BST* search(BST*, int);
	BST* Delete(BST*, int);
	//BST* Delete(BST*, BST*);
	BST* minValue(BST*);
	BST* maxValue(BST* node);
	//BST* inOrderSuccessor(BST* root, BST* n);
	int MAX_DIFF(BST* root);
	int MIN_DIFF(BST* root);
	void Inorder(BST*);
	void Inorder_Array(BST*, vector<int> &vect);
	int getData();
};
int BST::getData() {
	return this->data;
}
BST::BST()
	: data(0)
	, left(NULL)
	, right(NULL)
{
}

BST::BST(int value)
{
	data = value;
	left = right = NULL;
}

BST* BST::Insert(BST* root, int value)
{
	if (!root) {
		// Insert the first node, if root is NULL.
		return new BST(value);
	}

	if (value > root->data) {
		// Insert right node data, if the 'value'
		// to be inserted is greater than 'root' node data.

		// Process right nodes.
		root->right = Insert(root->right, value);
	}
	else {
		root->left = Insert(root->left, value);
	}
	return root;
}

void BST::Inorder(BST* root)
{
	if (!root) {
		return;
	}
	Inorder(root->left);
	cout << root->data << endl;
	Inorder(root->right);
}

void BST::Inorder_Array(BST* root, vector<int>& vect)
{
	if (!root) {
		return;
	}
	Inorder_Array(root->left,vect);
	//cout << root->data << endl;
	vect.push_back(root->data);
	Inorder_Array(root->right, vect);
}
BST*  BST::search(BST* root, int key)
{
	// Base Cases: root is null or key is present at root
	if (root == NULL || root->data == key)
		return root;

	// Key is greater than root's key
	if (root->data < key)
		return search(root->right, key);

	// Key is smaller than root's key
	return search(root->left, key);
}

BST* BST::minValue(BST* node) {
	BST* current = node;
	while (current && current->left != NULL) {
		current = current->left;
	}
	return current;
}
BST* BST::maxValue(BST* node) {
	BST* current = node;
	while (current && current->right != NULL) {
		current = current->right;
	}
	return current;
}
//BST* BST::inOrderSuccessor(BST* root, BST* n) {
//	if (n->right != NULL)
//		return minValue(n->right);
//
//	// step 2 of the above algorithm
//	struct node* p = n->parent;
//	while (p != NULL && n == p->right) {
//		n = p;
//		p = p->parent;
//	}
//	return p;
//}

BST* BST::Delete(BST* root, int key) {
	if (root == NULL)
		return root;
	if (key < root->data)
		root->left = Delete(root->left, key);

	else if (key > root->data)
		root->right = Delete(root->right, key);

	// if key is same as root key this node should be deleted
	else {
		//node has no child
		if (root->left == NULL && root->right == NULL)
			return NULL;
		// only 1 or no child
		else if (root->left == NULL) {
			BST* temp = root->right;
			return temp;
		}
		else if (root->right == NULL) {
			BST* temp = root->left;
			return temp;
		}
		// node with two children: Get the inorder successor
		// (smallest in the right subtree)
		BST* temp = minValue(root->right);

		// Copy the inorder successor's content to this node
		root->data = temp->data;

		// Delete the inorder successor
		root->right = Delete(root->right, temp->data);
	}
	return root;
}

int BST::MAX_DIFF(BST* root) {
	//need to check for distinct
	BST* minRoot = minValue(root);
	BST* maxRoot = maxValue(root);
	if ( minRoot == NULL or maxRoot == NULL or minRoot == maxRoot) return -1;

	int Min = minRoot->data;
	int Max = maxRoot->data;
	return abs(Min - Max);
}
int BST::MIN_DIFF(BST* root) {
	vector<int> vect;
	root->Inorder_Array(root, vect);
	if (vect.size() <= 2) {
		if (vect.size() == 2) {
			if (vect[0] == vect[1])
				return -1;
		}
		else return -1;
	}
	int minDif = INT_MAX;
	int temp;
	for (int i = 1; i < vect.size(); ++i) {
		temp = vect[i] - vect[i - 1];
		if (temp < minDif && temp)
			minDif = temp;
	}
	if (minDif == 0)
		return -1;
	return minDif;
}
int main()
{
	BST b, * root = NULL;
	/*root = b.Insert(root, 50);
	b.Insert(root, 30);
	b.Insert(root, 20);
	b.Insert(root, 40);
	b.Insert(root, 70);
	b.Insert(root, 60);
	b.Insert(root, 80);*/
	/*root = b.Insert(root, 1);
	b.Insert(root, 3);
	b.Insert(root, 7);
	cout << b.MAX_DIFF(root);*/

	ifstream f("zeap.in");
	//ifstream f("zeapin.txt");
	ofstream g("zeap.out");
	//ofstream g("zeapout.txt");
	string s;
	int val;

	//doamne fereste
	while (f >> s) {
		if (s == "I") {
			f >> val;
			if(!root)
			root = b.Insert(root, val);
			else b.Insert(root, val);
		}
		else if (s == "C") {
			f >> val;
			BST * temp = b.search(root, val);
			if (temp == NULL)
				cout << 0 << '\n';
			else cout << 1 << '\n';
		}
		else if (s == "S") {
			f >> val;
			BST* temp = b.search(root, val);
			if (temp != NULL)
				b.Delete(root, val);
			else cout << -1 << '\n';
		}
		else if (s == "MIN") {
			cout << b.MIN_DIFF(root) << '\n';
		}
		else if (s == "MAX") {
			cout << b.MAX_DIFF(root) << '\n';

		}

	}
	
	return 0;
}