#include<fstream>
#include<algorithm>
#include<cstdlib>
#include<ctime>
#include<cstring>
#define inf 0x3f3f3f3f
using namespace std;
ifstream f("zeap.in");
ofstream g("zeap.out");
struct Treap
{
int ma,mi,mad,mid,key,pr;
Treap *lef, *rig;
Treap() {}
Treap(int _ma,int _mi,int _mad,int _mid,int _key,int _pr,Treap *_lef,Treap *_rig)
{
ma=_ma;
mi=_mi;
mad=_mad;
mid=_mid;
key=_key;
pr=_pr;
lef=_lef;
rig=_rig;
}
};
Treap *R,*nil;
void init()
{
srand(time(0));
R=nil=new Treap(-inf,inf,-inf,inf,0,0,NULL,NULL);
nil->lef=nil->rig=nil;
}
void upd(Treap* &nod)
{
nod->mi=min(nod->key,min(nod->lef->mi,nod->rig->mi));
nod->ma=max(nod->key,max(nod->lef->ma,nod->rig->ma));
nod->mid= min(min(nod->lef->mid, nod->rig->mid) ,min( nod->key - nod->lef->ma , nod->rig->mi - nod->key ));
nod->mad= max(nod->ma - nod->mi,max(nod->lef->mad,nod->rig->mad));
}
void rotlef(Treap* &nod)
{
Treap *t= nod->lef;
nod->lef=t->rig;
t->rig=nod;
nod=t;
upd(nod);
upd(nod->rig);
}
void rotrig(Treap* &nod)
{
Treap *t = nod->rig;
nod->rig=t->lef;
t->lef=nod;
nod=t;
upd(nod);
upd(nod->lef);
}
void balance(Treap* &nod)
{
if(nod->lef->pr > nod->pr) rotlef(nod);
if(nod->rig->pr > nod->pr) rotrig(nod);
}
int find(Treap *nod,int key)
{
if(nod==nil) return 0;
if(nod->key == key) return 1;
if(nod->key < key) return find(nod->rig,key);
return find(nod->lef,key);
}
void insert(Treap* &nod, int key, int pr)
{
if(nod==nil)
{
nod=new Treap(key,key,-inf,inf,key,pr,nil,nil);
return ;
}
if(key < nod->key) insert(nod->lef,key,pr);
else
insert(nod->rig,key,pr);
balance(nod);
upd(nod);
}
void erase(Treap* &nod, int key)
{
if(nod==nil) return ;
if(key==nod->key)
{
if(nod->lef==nil&&nod->rig==nil)
{
delete(nod);
nod=nil;
return;
}
if(nod->lef->pr > nod->rig->pr)
{
rotlef(nod);
erase(nod->rig,key);
}
else
{
rotrig(nod);
erase(nod->lef,key);
}
}
else
{
if(key>nod->key)
erase(nod->rig,key);
else
erase(nod->lef,key);
}
upd(nod);
}
int main ()
{
int x;
string s;
init();
while(f>>s)
{
if(s=="C")
{
f>>x;
g<<find(R,x)<<"\n";
}
else
if(s=="I")
{
f>>x;
if(!find(R,x))
insert(R,x,rand()+1);
}
else
if(s=="S")
{
f>>x;
if(!find(R,x))
g<<"-1\n";
else
erase(R,x);
}
else
if(s=="MAX")
{
if(R->mad>-inf)
g<<R->mad<<"\n";
else
g<<"-1\n";
}
else
{
if(R->mid<inf)
g<<R->mid<<"\n";
else
g<<"-1\n";
}
}
return 0;
}