#include<stdio.h>
#include<stdlib.h>
#define Inf 1<<30
#define Min(a,b) a<b ? a : b
#define Red 1
#define Black 0
int N,i,nr,ok;
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;
RBT* Maxim(RBT *nod)
{
while(nod->right!=NIL)
nod=nod->right;
return nod;
}
RBT* Minim(RBT *nod)
{
while(nod->left!=NIL)
nod=nod->left;
return nod;
}
void update(RBT* &nod)
{
nod->dif_min = Min ( Min ( nod->left->dif_min, nod->right->dif_min ), Min ( abs(nod->key-nod->left->key), abs(nod->key-nod->right->key) ) );
}
void Rotate_Left(RBT* nod)
{
RBT* t=nod->right;
nod->right=t->left;
if(t->left!=NIL)
t->left->parent=nod;
t->parent=nod->parent;
if(nod->parent==NIL)
Root=t;
else
if(nod==nod->parent->left)
nod->parent->left=t;
else
nod->parent->right=t;
t->left=nod;
nod->parent=t;
update(t);
}
void Rotate_Right(RBT *nod)
{
RBT *t=nod->left;
nod->left=t->right;
if(t->right!=NIL)
t->right->parent=nod;
t->parent=nod->parent;
if(nod->parent==NIL)
Root=t;
else
if(nod==nod->parent->left)
nod->parent->left=t;
else
nod->parent->right=t;
t->right=nod;
nod->parent=t;
update(t);
}
void InsertFix(RBT* &nod)
{
if(nod==Root || nod->parent->color==Black)
{
Root->color=Black;
return ;
}
if(nod->parent==nod->parent->parent->left)
{
RBT *unchi=nod->parent->parent->right;
if(unchi->color==Red)
{
nod->parent->color=Black;
unchi->color=Black;
nod->parent->parent->color=Red;
InsertFix(nod->parent->parent);
}
else
{
if(nod==nod->parent->right)
{
nod=nod->parent;
Rotate_Left(nod);
}
nod->parent->color=Black;
nod->parent->parent->color=Red;
Rotate_Right(nod->parent->parent);
}
}
else
{
RBT *unchi=nod->parent->parent->left;
if(unchi->color==Red)
{
nod->parent->color=Black;
unchi->color=Black;
nod->parent->parent->color=Red;
InsertFix(nod->parent->parent);
}
else
{
if(nod==nod->parent->left)
{
nod=nod->parent;
Rotate_Right(nod);
}
nod->parent->color=Black;
nod->parent->parent->color=Red;
Rotate_Left(nod->parent->parent);
}
}
update(nod);
}
void Insert(RBT* &nod, RBT* p, int key)
{
if(Root==NIL)
{
Root = new RBT(key,Black,Inf,NIL,NIL,NIL);
N++;
return ;
}
if(nod==NIL)
{
nod = new RBT(key,Red,Inf,p,NIL,NIL);
N++;
InsertFix(nod);
}
else
{
if(key == nod->key) return;
if(key < nod->key) Insert(nod->left,nod,key);
else Insert(nod->right,nod,key);
}
//update(nod);
}
void EraseFix(RBT* &nod)
{
if(nod==Root || nod->color==Red)
{
nod->color=Red;
return;
}
if(nod==nod->parent->left)
{
RBT *frate=nod->parent->right;
if(frate->color==Red)
{
frate->color=Black;
nod->parent->color=Red;
Rotate_Left(nod->parent);
frate=nod->parent->right;
}
if(frate->left->color==Black && frate->right->color==Black)
{
frate->color=Red;
EraseFix(nod->parent);
}
else
{
if(frate->right->color==Black)
{
frate->left->color=Black;
frate->color=Red;
Rotate_Right(frate);
frate=nod->parent->right;
}
frate->color=nod->parent->color;
frate->parent->color=Black;
frate->right->color=Black;
Rotate_Left(nod->parent);
EraseFix(Root);
}
}
else
{
RBT *frate=nod->parent->left;
if(frate->color==Red)
{
frate->color=Black;
nod->parent->color=Red;
Rotate_Right(nod->parent);
frate=nod->parent->left;
}
if(frate->left->color==Black && frate->right->color==Black)
{
frate->color=Red;
EraseFix(nod->parent);
}
else
{
if(frate->left->color==Black)
{
frate->right->color=Black;
frate->color=Red;
Rotate_Left(frate);
frate=nod->parent->left;
}
frate->color=nod->parent->color;
nod->parent->color=Black;
frate->left->color=Black;
Rotate_Right(nod->parent);
EraseFix(Root);
}
}
update(nod);
}
void Erase(RBT* &nod, int key)
{
if(nod == NIL) {ok=0; return;}
if(nod->key==key)
{
RBT *x,*y;
if(nod->left==NIL || nod->right==NIL)
y=nod;
else y=Minim(nod->right);
if(y->left!=NIL)
x=y->left;
else
x=y->right;
x->parent=y->parent;
if(y->parent==NIL)
Root=x;
else
if(y==y->parent->left)
y->parent->left=x;
else
y->parent->right=x;
if(y!=nod)
nod->key=y->key;
if(y->color==Black)
EraseFix(x);
N--;
delete y;
y=NIL;
}
else
{
if(key < nod->key) Erase(nod->left,key);
else Erase(nod->right,key);
}
update(nod);
}
int find(RBT* nod, int key)
{
if(nod==NIL) return 0;
if(nod->key==key) return 1;
if(key < nod->key) return find(nod->left,key);
return find(nod->right,key);
}
int main()
{
freopen("zeap.in","r",stdin);
freopen("zeap.out","w",stdout);
NIL = Root = new RBT(-Inf,0,Inf,NULL,NULL,NULL);
while( !feof(stdin) )
{
scanf("%s",op);
if(op[0]=='I')
{
scanf("%d",&nr);
Insert(Root,Root,nr);
}
else if(op[0]=='S')
{
scanf("%d",&nr);
ok=1;
Erase(Root,nr);
if(!ok) printf("-1\n");
}
else if(op[0]=='C')
{
scanf("%d",&nr);
printf("%d\n",find(Root,nr));
}
else if(op[1]=='I')
{
if(N<2) printf("-1\n");
else
printf("%d\n",Root->dif_min);
}
else
{
if(N<2) printf("-1\n");
else
printf("%d\n",Maxim(Root)->key-Minim(Root)->key);
}
}
return 0;
}