#include <stdio.h>
#include <stdlib.h>
struct inr
{
int x,h;
inr *f[2];
}*rad,*nil,*hp;
int MAX(int a,int b)
{
return a>b?a:b;
}
void geth(inr *x)
{
x->h=MAX(x->f[0]->h,x->f[1]->h)+1;
}
inr *rot(inr *x,int z)
{
inr *aux=x->f[z];
x->f[z]=aux->f[1^z];
aux->f[1^z]=x;
geth(x);
geth(aux);
return aux;
}
inr *test(inr *x,int z)
{
if(x->f[z]->h>1+x->f[1^z]->h)
{
if(x->f[z]->f[1^z]->h>x->f[z]->f[z]->h)
x->f[z]=rot(x->f[z],1^z);
x=rot(x,z);
}
return x;
}
inr *balance(inr *x)
{
geth(x);
x=test(x,0);
x=test(x,1);
return x;
}
inr *insert(inr *x,int z)
{
if(x==nil)
{
x=(inr *)malloc(sizeof(inr));
x->f[0]=x->f[1]=nil;
x->x=z;
geth(x);
return x;
}
if(z<=x->x)
x->f[0]=insert(x->f[0],z);
else
x->f[1]=insert(x->f[1],z);
return balance(x);
}
inr *erase(inr *x,int z)
{
if(x==nil)
return x;
inr *aux;
if(x->x==z)
{
if(x->f[0]==nil||x->f[1]==nil)
{
aux=x->f[0]==nil?x->f[1]:x->f[0];
free(x);
return aux;
}
for(aux=x->f[0];aux->f[1]!=nil;aux=aux->f[1]);
x->x=aux->x;
x->f[0]=erase(x->f[0],aux->x);
return balance(x);
}
if(z<=x->x)
x->f[0]=erase(x->f[0],z);
else
x->f[1]=erase(x->f[1],z);
return balance(x);
}
int finds(inr *x)
{
}
void afis(inr *x)
{
if(x==nil)
return ;
afis(x->f[0]);
printf("%d\n",x->x);
afis(x->f[1]);
}
int find(inr *x,int z)
{
if(x==nil)
return 0;
if(x->x==z)
return 1;
return find(x->f[x->x<z],z);
}
int findl(inr *x,int z)
{
int aux;
if(x==nil)
return 0;
if(z<=x->x)
aux=findl(x->f[0],z);
else
aux=findl(x->f[1],z);
if(x->x>aux&&x->x<z)
aux=x->x;
return aux;
}
int findu(inr *x,int z)
{
int aux;
if(x==nil)
return 0;
if(z<x->x)
aux=findu(x->f[0],z);
else
aux=findu(x->f[1],z);
if((!aux||x->x<aux)&&x->x>z)
aux=x->x;
return aux;
}
int findm(inr *x,int z)
{
for(;x->f[z]!=nil;x=x->f[z]);
return x->x;
}
int init()
{
nil=(inr *)malloc(sizeof(inr));
nil->f[0]=nil->f[1]=NULL;
nil->x=0;
hp=rad=nil;
}
int main()
{
FILE *fi=fopen("zeap.in","r"),*fo=fopen("zeap.out","w");
int i,a,j;
char s[128];
init();
while(fgets(s,100,fi))
{
if(s[1]==' ')
for(a=0,i=2;s[i]>='0'&&s[i]<='9';++i)
a=a*10+s[i]-'0';
if(s[0]=='I')
if(!find(rad,a))
{
i=findl(rad,a);
j=findu(rad,a);
if(i&&j)
hp=erase(hp,j-i);
rad=insert(rad,a);
if(i)
hp=insert(hp,a-i);
if(j)
hp=insert(hp,j-a);
}
if(s[0]=='S')
if(find(rad,a))
{
i=findl(rad,a);
j=findu(rad,a);
if(i)
hp=erase(hp,a-i);
if(j)
hp=erase(hp,j-a);
if(i&&j)
hp=insert(hp,j-i);
rad=erase(rad,a);
}
else
fprintf(fo,"-1\n");
if(s[0]=='C')
fprintf(fo,"%d\n",find(rad,a));
if(s[1]=='A')
fprintf(fo,"%d\n",hp!=nil?findm(rad,1)-findm(rad,0):-1);
if(s[1]=='I')
fprintf(fo,"%d\n",hp!=nil?findm(hp,0):-1);
}
fclose(fi);
fclose(fo);
return 0;
}