#include<iostream>
#include<fstream>
#include<string.h>
#include<stdlib.h>
#include<time.h>
using namespace std;
 
#define INF (1<<30) - 100 + (1<<30)
 
class Treap {
    int info,priority,maxim,minim,difmin;
    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);
	void compute_difmin(Treap *nod);
	int dif_min(Treap *nod);
	int dif_max(Treap *nod);
};
 
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->maxim = _info;
	this->minim = _info;
	this->difmin = INF;
    this->left = _left;
    this->right = _right;
}

void Treap :: compute_difmin(Treap *nod)
{
	if(nod->left->info==0 && nod->right->info==0) {
		nod->maxim=nod->info;
		nod->minim=nod->info;
		nod->difmin = INF;
		return;
	}
	if(nod->left->info==0) {
		nod->minim=nod->info;
		nod->maxim=nod->right->maxim;
		nod->difmin=min(nod->right->difmin,nod->right->minim - nod->info);
		return ;
	}
	if(nod->right->info==0) {
		nod->minim=nod->left->minim;
		nod->maxim=nod->info;
		nod->difmin=min(nod->left->difmin,nod->info - nod->left->maxim);
		return ;
	}
	nod->minim=nod->left->minim;
	nod->maxim=nod->right->maxim;
	nod->difmin=min(min(nod->left->difmin,nod->right->difmin),min(nod->right->minim - nod->info,nod->info - nod->left->maxim));
	return;
}

void Treap :: balance(Treap *&nod) {
    if(nod->left->priority>nod->priority)
        rot_right(nod);
    else if(nod->right->priority>nod->priority)
        rot_left(nod);
	compute_difmin(nod);
}
 
void Treap :: rot_left(Treap *&nod) {
    Treap *aux = nod->right;
    nod->right = aux->left;
    aux->left = nod;
	compute_difmin(nod);
	compute_difmin(aux);
    nod = aux;
}
     
void Treap :: rot_right(Treap *&nod) {
    Treap *aux = nod->left;
    nod->left = aux->right;
    aux->right = nod;
	compute_difmin(nod);
	compute_difmin(aux);
    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);
    }
	if(nod!=nil)
		compute_difmin(nod);
}

int Treap :: dif_min(Treap *nod)
{
	if(nod->right==nil)
		return -1;
	if(nod->right->difmin==INF)
		return -1;
	return nod->right->difmin;
}

int Treap :: dif_max(Treap *nod)
{
	if(nod->right==nil)
		return -1;
	if(nod->right->minim == nod->right->maxim)
		return -1;
	return nod->right->maxim - nod->right->minim;
}

 
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(p)<<'\n';
		else g<<p->dif_min(p)<<'\n';
	}
	f.close();
	g.close();
	return 0;
}