#include<fstream>
#include<stdlib.h>
#define Min(a,b) a<b ? a : b
#define Inf 1<<30
#define Black 0
#define Red 1
using namespace std;
int i,N,nr,ok,sol;
char op[4];
struct RBT
{
int key,color,dif_min;
RBT *parent, *left, *right;
RBT() {}
RBT(int key, int color, int dif_min, RBT *parent, RBT *left, RBT *right)
{
this->key=key;
this->color=color;
this->dif_min=dif_min;
this->parent=parent;
this->left=left;
this->right=right;
}
} *Root, *NIL, *z;
RBT* Minim(RBT *x)
{
while(x->left!=NIL)
x=x->left;
return x;
}
RBT* Maxim(RBT *x)
{
while(x->right!=NIL)
x=x->right;
return x;
}
void update(RBT *nod)
{
int a, b;
if(nod!=NIL)
{
a = Min( nod->right->dif_min, nod->left->dif_min ) ;
b = Min( abs(nod->key-nod->right->key), abs(nod->key-nod->left->key) );
nod->dif_min = Min(a,b);
}
}
void Update(RBT *nod)
{
update(nod);
if(nod->parent!=NIL) Update(nod->parent);
}
int find(RBT *x, int key)
{
if(x==NIL) return 0;
if(x->key==key) return 1;
if(key < x->key) return find(x->left,key);
return find(x->right,key);
}
void rotleft(RBT *n)
{
RBT *t=n->right;
n->right=t->left;
if(t->left!=NIL)
t->left->parent=n;
t->parent=n->parent;
if(t->parent==NIL) Root=t;
else
if( n == n->parent->left)
n->parent->left=t;
else
n->parent->right=t;
t->left=n;
n->parent=t;
//Update(n);
}
void rotright(RBT *n)
{
RBT *t=n->left;
n->left=t->right;
if(t->right!=NIL)
t->right->parent=n;
t->parent=n->parent;
if(t->parent==NIL) Root=t;
else
if( n == n->parent->left)
n->parent->left=t;
else
n->parent->right=t;
t->right=n;
n->parent=t;
//Update(n);
}
void InsertFix(RBT *x)
{
if( x==Root || x->parent->color==Black )
{
Root->color=Black;
return ;
}
if( x->parent == x->parent->parent->left)
{
RBT *y = x->parent->parent->right;
if( y->color == Red )
{
x->parent->color=Black;
y->color=Black;
x->parent->parent->color=Red;
InsertFix(x->parent->parent);
}
else
{
if( x == x->parent->right)
{
x=x->parent;
rotleft(x);
}
x->parent->color=Black;
x->parent->parent->color=Red;
rotright(x->parent->parent);
}
}
else
{
RBT *y = x->parent->parent->left;
if( y->color == Red )
{
x->parent->color=Black;
y->color=Black;
x->parent->parent->color=Red;
InsertFix(x->parent->parent);
}
else
{
if( x == x->parent->left )
{
x=x->parent;
rotright(x);
}
x->parent->color=Black;
x->parent->parent->color=Red;
rotleft(x->parent->parent);
}
}
}
void Insert(RBT *&n, RBT *p, int key)
{
if( Root == NIL )
{
Root = new RBT(key,Black,Inf,NIL,NIL,NIL);
N++;
return ;
}
if( n == NIL )
{
n = new RBT(key,Red,Inf,p,NIL,NIL);
N++;
//Update(p);
InsertFix(n);
return;
}
if( key == n->key ) return ;
if( key < n->key ) Insert(n->left,n,key);
else Insert(n->right,n,key);
}
void EraseFix(RBT *x)
{
if( x == Root || x->color == Red )
{
x->color=Black;
return ;
}
if( x==x->parent->left )
{
RBT *w = x->parent->right;
if( w->color == Red )
{
w->color=Black;
x->parent->color=Red;
rotleft(x->parent);
w=x->parent->right;
}
if( w->left->color == Black && w->right->color == Black )
{
w->color=Red;
EraseFix(x->parent);
}
else
{
if( w->right->color == Black )
{
w->left->color=Black;
w->color=Red;
rotright(w);
w=x->parent->right;
}
w->color=x->parent->color;
x->parent->color=Black;
w->right->color=Black;
rotleft(x->parent);
EraseFix(Root);
}
}
else
{
RBT *w = x->parent->left;
if( w->color == Red )
{
w->color=Black;
x->parent->color=Red;
rotright(x->parent);
w=x->parent->left;
}
if( w->left->color == Black && w->right->color == Black )
{
w->color=Red;
EraseFix(x->parent);
}
else
{
if( w->left->color == Black )
{
w->right->color=Black;
w->color=Red;
rotleft(w);
w=x->parent->left;
}
w->color=x->parent->color;
x->parent->color=Black;
w->left->color=Black;
rotright(x->parent);
EraseFix(Root);
}
}
}
void Erase( RBT *&n, int key )
{
if( n == NIL )
{
ok=0;
return;
}
if( n->key == key )
{
RBT *x,*y,*yp;
int col,st=0; N--;
z->parent = n->parent;
z->left = n->left;
z->right = n->right;
if( n->parent != NIL && n == n->parent->left ) st=1;
if( n->left == NIL && n->right == NIL )
{
if( n == Root )
{
delete n;
n=NIL;
return ;
}
col=n->color;
delete n;
n=NIL;
NIL->parent=z->parent;
if(st==1)
z->parent->left = NIL;
else
z->parent->right = NIL;
if(col==Black)
EraseFix(NIL);
return ;
}
if( n->right == NIL ) y = n->left;
else
y=Minim(n->right);
col = y->color;
y->color = n->color;
x=y->right;
yp=y->parent;
if(y->parent == n)
{
delete n;
n=NIL;
y->parent = z->parent;
if(z->parent!=NIL)
if(st) y->parent->left=y;
else y->parent->right=y;
else Root=y;
if(y!=z->left)
{
y->left=z->left;
y->left->parent=y;
}
//Update(y);
if(col==Black)
{
x->parent=y;
EraseFix(x);
}
}
else
{
y->parent->left=x;
delete n;
n=NIL;
y->parent = z->parent;
if(z->parent!=NIL)
if(st) y->parent->left=y;
else y->parent->right=y;
else Root=y;
y->left = z->left;
y->left->parent=y;
y->right=z->right;
y->right->parent=y;
//Update(y);
//Update(x->parent);
if(col==Black)
{
x->parent=yp;
EraseFix(x);
}
}
}
else
if( key < n->key ) Erase(n->left,key);
else
Erase(n->right,key);
}
int v[300010],P;
void dfs(RBT *nod)
{
if(nod==NIL) return ;
dfs(nod->left);
v[++P] = nod->key;
dfs(nod->right);
}
void Dif_min(RBT *nod)
{
P=0;
dfs(nod);
for(i=2;i<=P;i++)
if(v[i]-v[i-1]<sol) sol=v[i]-v[i-1];
}
ifstream f("zeap.in");
ofstream g("zeap.out");
void afisaza(RBT *p)
{
if(p==NIL) return ;
afisaza(p->left);
g<<p->key<<"("<<p->color<<")";
if(p==Root) g<<"-0 ";
else g<<"-"<<p->parent->key<<" ";
afisaza(p->right);
}
int main()
{
NIL = Root = z = new RBT(-Inf,0,Inf,NULL,NULL,NULL);
while( f>>op )
{
if(op[0]=='I')
{
f>>nr;
Insert(Root,Root,nr);
}
else if(op[0]=='S')
{
f>>nr;
ok=1;
Erase(Root,nr);
if(!ok) g<<"-1\n";
}
else if(op[0]=='C')
{
f>>nr;
g<<find(Root,nr)<<'\n';
}
else if(op[1]=='I')
{
if(N<2) g<<"-1\n";
else
//g<<Root->dif_min<<'\n';
{
sol=Inf;
Dif_min(Root);
g<<sol<<'\n';
}
}
else
{
if(N<2) g<<"-1\n";
else
g<<Maxim(Root)->key-Minim(Root)->key<<'\n';
}
}
//afisaza(Root);
f.close();
g.close();
return 0;
}