#include <fstream>
#include <iostream>
#include <string>
#include <limits>
using namespace std;

class Zeap
{
	struct node
	{
		int data;
		node* left, * right;
		node* parent;
		node(int x, node* parent) : data(x), left(), right(), parent(parent) {}
		~node()
		{
			delete left;
			delete right;
		}
	};

	size_t size;
	node* root;
	int max,min,p_elem,s_elem;

	node* predecessor(node* crt_node)
	{
		if (crt_node->data == min)
			return nullptr;
		if (crt_node->left != nullptr)
		{
			crt_node = crt_node->left;
			while (crt_node->right != nullptr)
				crt_node = crt_node->right;
		}
		else
		{
			node* src_node = crt_node;
			crt_node = crt_node->parent;
			while (crt_node!=nullptr&& crt_node->data > src_node->data)
				crt_node = crt_node->parent;
		}

		return crt_node;
	}
	node* successor(node* crt_node)
	{
		if (crt_node->data == max)
			return nullptr;
		if (crt_node->right != nullptr)
		{
			crt_node = crt_node->right;
			while (crt_node->left != nullptr)
				crt_node = crt_node->left;
		}
		else
		{
			node* src_node = crt_node;
			crt_node = crt_node->parent;
			while (crt_node != nullptr && crt_node->data < src_node->data)
				crt_node = crt_node->parent;
		}
		return crt_node;
	}
	void restructureMin()
	{
		if (size < 2)
			return;
		int min_dif = -1;
		node* crt_node = nodeSearch(min);
		node* succ = successor(crt_node);
		while (succ != nullptr)
		{
			int dif = abs(succ->data - crt_node->data);
			if (dif < min_dif || min_dif == -1)
			{
				min_dif = dif;
				s_elem = succ->data;
				p_elem = crt_node->data;
			}
			crt_node = succ;
			succ = successor(crt_node);
		}
	}

	node* nodeSearch(const int& x) const
	{
		node* crt_node = root;
		if (crt_node == nullptr)
			return nullptr;
		while (crt_node->data != x)
		{

			if (crt_node->data < x)
				if (crt_node->right != nullptr)
					crt_node = crt_node->right;
				else
					return crt_node;
			else
			{
				if (crt_node->left != nullptr)
					crt_node = crt_node->left;
				else
					return crt_node;
			}

		}
		return crt_node;
	}
	static void removeFromParent(node* crt_node)
	{
		node* par = crt_node->parent;
		if (par != nullptr)
		{
			if (par->left == crt_node)
				par->left = nullptr;
			else
				par->right = nullptr;
		}
	}


public:
	Zeap() :size(), root(), max(0), min(numeric_limits<int>::max()), p_elem(0), s_elem(0) {}
	int maxDif() const
	{
		if (size > 1)
			return abs(max - min);
		else
			return -1;
	}
	int minDif() const
	{
		if (size > 1)
			return abs(s_elem - p_elem);
		else
			return -1;
	}

	bool search(const int& x) const
	{
		node* found = nodeSearch(x);
		if (found!=nullptr && found->data == x)
			return true;
		else
			return false;
	}

	void insert(const int& x)
	{

		node* crt_node = nodeSearch(x);
		if (crt_node == nullptr || crt_node->data != x)
		{
			++size;
			if (crt_node == nullptr)
			{
				root = new node(x, nullptr);
				p_elem = max = min = root->data;
				
			}
			else
			{

				if (crt_node->data < x)
					crt_node = crt_node->right = new node(x, crt_node);
				else
					crt_node = crt_node->left = new node(x, crt_node);

				if (crt_node->data > max)
					max = crt_node->data;
				if (crt_node->data < min)
					min = crt_node->data;
				if (size == 2)
				{
					if (crt_node->data > root->data)
					{
						s_elem = crt_node->data;
						p_elem = root->data;
					}
					else
					{
						s_elem = root->data;
						p_elem = crt_node->data;
					}
				}
				else
				{
					node* pred = predecessor(crt_node);
					node* succ = successor(crt_node);
					int min_dif = minDif();
					if (pred != nullptr && abs(crt_node->data - pred->data) < min_dif)
					{
						s_elem = crt_node->data;
						p_elem = pred->data;
					}
					if (succ != nullptr && abs(crt_node->data - succ->data) < min_dif)
					{
						s_elem = succ->data;
						p_elem = crt_node->data;
					}
				}
			}
		}
	}

	int remove(const int& x)
	{
		node* crt_node = nodeSearch(x);
		if (crt_node == nullptr || crt_node->data != x)
			return -1;
		else
		{
			--size;
			bool restructure = false;
			const int data = crt_node->data;
			if (crt_node->data == max)
			{
				node* pred = predecessor(crt_node);
				max = pred!=nullptr? pred->data : -1;
			}
			if (crt_node->data == min)
			{
				node* succ = successor(crt_node);
				min = succ != nullptr ? succ->data : numeric_limits<int>::max();
			}
			if (crt_node->data == p_elem || crt_node->data == s_elem)
				restructure = true;
			if (crt_node->left == nullptr && crt_node->right == nullptr)
			{
				removeFromParent(crt_node);
				delete crt_node;
			}
			else
			{
				node* rep = predecessor(crt_node);
				if (crt_node->left == nullptr)
				{
					rep = successor(crt_node);
					removeFromParent(rep);
					crt_node->data = rep->data;
					node* rep_it = rep;
					while (rep_it->right != nullptr)
						rep_it = rep_it->right;
					if (crt_node->right != nullptr)
					{
						rep_it->right = crt_node->right;    
						crt_node->right->parent = rep_it;  

					}
					crt_node->right = rep->right;
					if (crt_node->right != nullptr)
						crt_node->right->parent = crt_node;
					rep->right = nullptr;
					delete rep;

				}
				else
				{
					crt_node->data = rep->data;
					node* rep_it = rep;
					removeFromParent(rep);
					while (rep_it->left != nullptr)
						rep_it = rep_it->left;
														
					if (crt_node->left != nullptr)
					{
						rep_it->left = crt_node->left;
						crt_node->left->parent = rep_it;
					}
					crt_node->left = rep->left;
					if(crt_node->left!=nullptr)
						crt_node->left->parent = crt_node;
					rep->left = nullptr;
					delete rep;
				}
				if (restructure)
					restructureMin();
			}
			if (size == 0)
				root = nullptr;
			return data;


		}

	}

};

enum class commands
{
	ins,
	rem,
	src,
	max,
	min
};

void resolveCommand(const string& input, commands& cmd, int& par)
{
	switch (input[0])
	{
	case 'I':
	{
		cmd = commands::ins;
		par = stoi(&input[2]);
		return;
	}
	case 'S':
	{
		cmd = commands::rem;
		par = stoi(&input[2]);
		return;
	}
	case 'C':
	{
		cmd = commands::src;
		par = stoi(&input[2]);
		return;
	}
	case 'M':
	{
		if (input[1] == 'I')
		{
			cmd = commands::min;
			return;
		}
		else
		{
			cmd = commands::max;
			return;
		}
	}
	default:
		break;
	}
}

int main()
{

	ifstream in("zeap.in");
	ofstream out("zeap.out");
	Zeap my_zeap;
	string input;
	commands cmd;
	int param;
	while (getline(in, input))
	{
		resolveCommand(input, cmd, param);
		switch (cmd)
		{
		case commands::ins:
		{
			my_zeap.insert(param);
			break;
		}
		case commands::rem:
		{
			int res = my_zeap.remove(param);
			if (res == -1)
				out << "-1\n";
			break;
		}
		case commands::src:
		{
			out << my_zeap.search(param) << "\n";
			break;
		}
		case commands::min:
		{
			out << my_zeap.minDif() << "\n";
			break;
		}
		case commands::max:
		{
			out << my_zeap.maxDif() << "\n";
			break;
		}
		}
	}
	return 0;
}