#include <bits/stdc++.h>
#define MaxN 100005
#define INF 2140000000
#define MOD 1000000007
using namespace std;
FILE*IN,*OUT;
int N,X,Y;
char C[10];
struct Treap
{
int priority,value,weight,Min,Max,MinDif;
Treap *left,*right;
Treap(int val=-1,Treap *NILL=NULL)
{
Max=Min=val;
if(val==-1)
Min=INF;
MinDif=INF;
priority=rand();
value=val;
if(val==-1)
weight=0;
else weight=1;
left=right=NILL;
}
}*NIL;
void recalculate(Treap *T)
{
T->weight=1+T->left->weight+T->right->weight;
T->Max=max(T->value,max(T->left->Max,T->right->Max));
T->Min=min(T->value,min(T->left->Min,T->right->Min));
T->MinDif=min(T->left->MinDif,T->right->MinDif);
if(T->left!=NIL)
T->MinDif=min(T->MinDif,T->left->Min-T->value);
if(T->right!=NIL)
T->MinDif=min(T->MinDif,T->value-T->right->Max);
}
Treap *join(Treap *Treap1,Treap *Treap2)
{
if(Treap1==NIL)
return Treap2;
if(Treap2==NIL)
return Treap1;
if(Treap1->priority>=Treap2->priority)
{
Treap1->left=join(Treap1->left,Treap2);
recalculate(Treap1);
return Treap1;
}
else
{
Treap2->right=join(Treap1,Treap2->right);
recalculate(Treap2);
return Treap2;
}
}
pair<Treap*,Treap*> split(Treap *T,int val)
{
if(T==NIL)
return make_pair(NIL,NIL);
if(T->value>val)
{
pair<Treap*,Treap*>Temp;
Temp=split(T->right,val);
T->right=Temp.second;
T->MinDif=INF;
recalculate(T);
return make_pair(Temp.first,T);
}
else
{
pair<Treap*,Treap*>Temp;
Temp=split(T->left,val);
T->left=Temp.first;
T->MinDif=INF;
recalculate(T);
return make_pair(T,Temp.second);
}
}
void Insert(Treap*&T,int val)
{
Treap* Added=new Treap(val,NIL);
pair<Treap*,Treap*>Temp=split(T,val);
T=join(Temp.first,join(Added,Temp.second));
}
void Delete(Treap *&T,int key)
{
pair<Treap*,Treap*>Temp=split(T,key-1);
pair<Treap*,Treap*>Temp2=split(Temp.second,key);
T=join(Temp.first,Temp2.second);
}
bool GetPos(Treap*T,int val)
{
bool p=true;
if(T==NIL)
return 0;
if(T->value<val)
p&=GetPos(T->left,val);
else if(T->value==val)
return 1;
else
p&=GetPos(T->right,val);
return p;
}
void WalkThrough(Treap*T)
{
if(T->right!=NIL)
WalkThrough(T->right);
fprintf(OUT,"%d ",T->value);
if(T->left!=NIL)
WalkThrough(T->left);
}
int main()
{
IN=fopen("zeap.in","r");
OUT=fopen("zeap.out","w");
srand(time(NULL));
NIL=new Treap();
Treap*Root=NIL;
while(fscanf(IN,"%s ",C)!=EOF)
{
if(C[0]=='I')
{
fscanf(IN,"%d ",&X);
if(GetPos(Root,X)==0)
Insert(Root,X);
}
else if(C[0]=='S')
{
fscanf(IN,"%d ",&X);
if(GetPos(Root,X))
Delete(Root,X);
else fprintf(OUT,"-1\n");
}
else if(C[0]=='C')
{
fscanf(IN,"%d ",&X);
bool x=GetPos(Root,X);
if(x==0)
fprintf(OUT,"0\n");
else fprintf(OUT,"1\n");
}
else if(C[1]=='A')
{
if(Root->weight==1)
fprintf(OUT,"-1\n");
else fprintf(OUT,"%d\n",Root->Max-Root->Min);
}
else
{
if(Root->weight==1)
fprintf(OUT,"-1\n");
else fprintf(OUT,"%d\n",Root->MinDif);
}
}
return 0;
}