#include<iostream>
#include<fstream>
#include<string.h>
#include<stdlib.h>
#include<time.h>
using namespace std;

#define INF 1<<30

class Treap {
	int info,priority;
	Treap *left,*right;
	
public :

	Treap (int _info, int _priority, Treap *_left, Treap *_right);
	Treap () {}
	void rot_left(Treap *&nod);
	void balance(Treap *&nod);
	void rot_right(Treap *&nod);
	void insert(Treap *&nod, int _info, int _priority);
	int search(Treap *nod, int _info);
	void erase(Treap *&nod, int _info) ;
	int dif_max();
};

Treap *nil = new Treap(0,0,NULL,NULL);

Treap :: Treap (int _info, int _priority, Treap *_left, Treap *_right) {
	this->info=_info;
	this->priority=_priority;
	this->left=_left;
	this->right=_right;
}

void Treap :: balance(Treap *&nod) {
	if(nod->left->priority>nod->priority)
		rot_right(nod);
	else if(nod->right->priority>nod->priority)
		rot_left(nod);
}

void Treap :: rot_left(Treap *&nod) {
	Treap *aux = nod->right;
	nod->right = aux->left;
	aux->left = nod;
	nod = aux;
}
	
void Treap :: rot_right(Treap *&nod) {
	Treap *aux = nod->left;
	nod->left = aux->right;
	aux->right = nod;
	nod = aux;
}
	
void Treap :: insert(Treap *&nod, int _info, int _priority) {
	if(nod==nil) {
		nod=new Treap(_info,_priority,nil,nil);
		return ;
	}
	if(_info<=nod->info)
		insert(nod->left,_info,_priority);
	else insert(nod->right,_info,_priority);
	balance(nod);
}
	
int Treap :: search(Treap *nod, int _info) {
	if(nod==nil)
		return 0;
	if(nod->info==_info)
		return 1;
	if(_info<=nod->info)
		return search(nod->left,_info);
	else return search(nod->right,_info);
}
	
void Treap :: erase(Treap *&nod, int _info) {
	if(nod==nil)
		return ;
		
	if(_info<nod->info)
		erase(nod->left,_info);
	else if(_info>nod->info)
		erase(nod->right,_info);
	else {
		if(nod->left==nil && nod->right==nil) {
			delete nod;
			nod=nil;
			return ;
		}
		if(nod->left->priority>nod->right->priority)
			rot_right(nod);
		else rot_left(nod);
		
		erase(nod,_info);
	}
}

int Treap :: dif_max()
{
	int max,min;
	Treap *nod = this->right;
	Treap *aux = this->right;
	max = min = nod->info;
	while(aux->right!=nil) {
		aux=aux->right;
		if(aux->info>max)
			max=aux->info;
	}
	while(aux->left!=nil) {
		aux=aux->left;
		if(aux->info<min)
			min=aux->info;
	}
	return max-min;
}

Treap *p = new Treap(0,INF,nil,nil);
char op[5];

int main ()
{
	int x;
	ifstream f("zeap.in");
	ofstream g("zeap.out");
	srand(time(NULL));
	while(f.peek()!=EOF) {
		f>>op;
		if(op[0]=='I') {
			f>>x;
			if(p->search(p,x)==0)
				p->insert(p,x,rand()+1);
		}
		else if(op[0]=='S') {
			f>>x;
			if(p->search(p,x)==1)
				p->erase(p,x);
			else g<<"-1\n";
		}
		else if(op[0]=='C') {
			f>>x;
			g<<p->search(p,x)<<'\n';
		}
		else if(strcmp(op,"MAX")==0)
			g<<p->dif_max()<<'\n';
		else g<<"0\n";
	}
	f.close();
	g.close();
	return 0;
}