#include <bits/stdc++.h>
#define MOD 666013
using namespace std;
int x,nr;
char c;
struct Treap
{
int key,pr;
Treap *l,*r;
int ma,mi,dif;
Treap(int key1,int pr1,int ma1,int mi1,int dif1,Treap *l1,Treap *r1)
{
key=key1;
pr=pr1;
ma=ma1;
mi=mi1;
dif=dif1;
l=l1;
r=r1;
}
}*R,*nil;
void Update(Treap *&R)
{
R->ma=max(R->key,R->r->ma);
R->mi=min(R->key,R->l->mi);
R->dif=min(min(R->l->dif,R->r->dif),min(abs(R->key-R->l->ma),abs(R->key-R->r->mi)));
}
void rotleft(Treap *&R)
{
Treap *aux=R->l;
R->l=aux->r;
aux->r=R;
R=aux;
if(R!=nil)
{
if(R->r!=nil)Update(R->r);
}
}
void rotright(Treap *&R)
{
Treap *aux=R->r;
R->r=aux->l;
aux->l=R;
R=aux;
if(R!=nil)
{
if(R->l!=nil)Update(R->l);
}
}
void balance(Treap *&R)
{
if(R->pr<R->l->pr)rotleft(R);
else if(R->pr<R->r->pr)rotright(R);
Update(R);
}
int Cauta(Treap* node,int key)
{
if(node==nil) return 0;
if(node->key==key) return 1;
if(key<node->key) return Cauta(node->l,key);
if(key>node->key) return Cauta(node->r,key);
}
void Insereaza(Treap *&R,int val,int pr)
{
if(R==nil)
{
R=new Treap(val,pr,val,val,INT_MAX,nil,nil);
nr++;
return ;
}
if(val<R->key)Insereaza(R->l,val,pr);
else Insereaza(R->r,val,pr);
balance(R);
}
void Sterge(Treap *&R,int val)
{
if(val<R->key)Sterge(R->l,val);
else if(val>R->key)Sterge(R->r,val);
else
{
if(R->r==nil&&R->l==nil)
{
delete R;
R=nil;
--nr;
return ;
}
else
{
if(R->l->pr>R->r->pr)rotleft(R);
else rotright(R);
Sterge(R,val);
}
}
if(R!=nil)Update(R);
}
int main()
{
ifstream f ("zeap.in");
ofstream g ("zeap.out");
srand(time(0));
R=nil=new Treap(0,0,INT_MIN,INT_MAX,INT_MAX,NULL,NULL);
while(f>>c)
if(c=='I')
{
f>>x;
if(!Cauta(R,x))Insereaza(R,x,rand()%MOD+1);
}
else if(c=='S')
{
f>>x;
if(Cauta(R,x))Sterge(R,x);
else g<<-1<<'\n';
}
else if(c=='C')
{
f>>x;
g<<Cauta(R,x)<<'\n';
}
else if(c=='M')
{
f>>c;
f>>c;
if(nr<2)
{
g<<-1<<'\n';
continue;
}
if(c=='N')g<<R->dif<<'\n';
else g<<R->ma-R->mi<<'\n';
}
return 0;
}