#include <iostream>
#include <ctime>
#include <cstdlib>
#include <cstdio>
using namespace std;
const int INF = 0x3f3f3f3f;
int n;
struct Treap
{
int key, priority;
int minim, maxim, mindif;
Treap *left, *right;
Treap(){}
Treap(int key,int priority,Treap *left, Treap *right)
{
this->key = key, this->priority = priority, this->left = left, this->right = right;
maxim = -INF, minim= INF, mindif =INF;
}
}*root,*nil;
void solve();
int main()
{
srand(time(0));
solve();
return 0;
}
void left_rot(Treap *&node)
{
Treap *aux = node->left;
node->left = aux->right;
aux->right = node;
node = aux;
}
void right_rot(Treap *&node)
{
Treap *aux = node->right;
node->right = aux->left;
aux->left = node;
node = aux;
}
void update(Treap* &node)
{
if(node == nil)
return;
node->minim = min(node->key, node->left->minim);
node->maxim = max(node->key, node->right->maxim);
node->mindif = min(min(node->left->mindif, node->right->mindif),\
min(node->key - node->left->maxim, node->right->minim - node->key));
}
void balance(Treap *&node)
{
if(node->left->priority > node->priority)
{
left_rot(node);
update(node->right);
}
else if(node->right->priority > node->priority)
{
right_rot(node);
update(node->left);
}
update(node);
}
void ins(Treap *&node, int key)
{
if(node == nil)
{
node = new Treap(key,rand()+1,nil,nil);
node->maxim = node->minim = key;
n++;
return;
}
if(key < node->key)
ins(node->left,key);
else ins(node->right, key);
balance(node);
update(node);
}
bool src(Treap *node,int key)
{
if(node == nil)
return 0;
if(node->key == key)
return 1;
if(key < node->key)
return src(node->left,key);
return src(node->right, key);
}
void rm(Treap* &node,int key)
{
if(node == nil)
return;
if(key < node->key)
rm(node->left, key);
else if( key > node->key)
rm(node->right, key);
else
{
if(node->left == nil && node->right == nil)
{
--n;
delete node;
node = nil;
return;
}
else
{
if(node->left->priority > node->right->priority)
left_rot(node);
else
right_rot(node);
rm(node,key);
}
}
update(node);
}
char s[20];
void solve()
{
root = nil = new Treap(0,0,0,0);
freopen("zeap.in","r",stdin);
freopen("zeap.out","w",stdout);
while(gets(s))
{
if(*s == 'I')
{
int key;
sscanf(s+2,"%d",&key);
ins(root,key);
}
else if(*s == 'S')
{
int key;
sscanf(s+2,"%d",&key);
if(!src(root,key))
printf("-1\n");
else rm(root,key);
}
else if(*s == 'C')
{
int key;
sscanf(s+2,"%d",&key);
printf("%d\n",src(root,key));
}
else if(*s == 'M')
{
if(n<2)
{
printf("-1\n");
}
else
{
if(s[1] == 'A')
{
printf("%d\n",root->maxim - root->minim);
}
else
{
printf("%d\n",root->mindif);
}
}
}
}
}