#include <cstdio>
#include <algorithm>
#include <ctime>
#include <cstdlib>
const int DIM = 1 << 3;
const int INF = 0x3f3f3f3f;
using namespace std;
class nrx_treap {
private:
int _treap_size = 0;
struct treap_node {
int key, priority, min_difference, maxim, minim;
treap_node *left_node, *right_node;
treap_node( int key, int priority, int min_difference, int maxim, int minim, treap_node *left_node, treap_node *right_node ) {
this -> key = key; this -> priority = priority; this -> min_difference = min_difference; this -> maxim = maxim;
this -> left_node = left_node; this -> right_node = right_node; this -> minim = minim;
}
} *root, *empty_node;
void update_max( treap_node* &node ) {
node -> maxim = max( node -> key, node -> right_node -> maxim );
return;
}
void update_min( treap_node* &node ) {
node -> minim = min( node -> key, node -> left_node -> minim );
return;
}
void update_min_difference( treap_node* &node ) {
node -> min_difference = min( node -> key - node -> left_node -> maxim, node -> right_node -> minim - node -> key );
node -> min_difference = min( node -> min_difference, node -> left_node -> min_difference );
node -> min_difference = min( node -> min_difference, node -> right_node -> min_difference );
return;
}
void update_node( treap_node* &node ) {
update_max( node ); update_min( node );
update_min_difference( node );
return;
}
void rotate_left( treap_node* &node ) {
treap_node *aux_node = node -> left_node;
node -> left_node = aux_node -> right_node;
aux_node -> right_node = node; node = aux_node;
update_node( node -> right_node );
update_node( node );
return;
}
void rotate_right( treap_node* &node ) {
treap_node *aux_node = node -> right_node;
node -> right_node = aux_node -> left_node;
aux_node -> left_node = node; node = aux_node;
update_node( node -> left_node );
update_node( node );
return;
}
void balance( treap_node* &node ) {
if( node -> left_node -> priority > node -> priority )
rotate_left( node );
else
if( node -> right_node -> priority > node -> priority )
rotate_right( node );
return;
}
int search_node( treap_node* &node, int key ) {
if( node == empty_node )
return -1;
if( node -> key == key )
return 1;
if( node -> key > key )
return search_node( node -> left_node, key );
else
return search_node( node -> right_node, key );
return -1;
}
int insert_node( treap_node* &node, int key ) {
if( node == empty_node ) {
_treap_size ++;
node = new treap_node( key, rand() + 1, INF, key, key, empty_node, empty_node );
return 1;
}
if( node -> key == key )
return -1;
int ok;
if( node -> key > key )
ok = insert_node( node -> left_node, key );
else
ok = insert_node( node -> right_node, key );
update_node( node ); balance( node );
return ok;
}
int delete_node( treap_node* &node, int key ) {
if( node == empty_node )
return -1;
int ok;
if( node -> key > key ) {
ok = delete_node( node -> left_node, key );
update_node( node );
return ok;
}
if( node -> key < key ) {
ok = delete_node( node -> right_node, key );
update_node( node );
return ok;
}
if( node -> left_node == empty_node && node -> right_node == empty_node ) {
delete node; node = empty_node;
_treap_size --;
} else {
if( node -> left_node -> priority > node -> right_node -> priority ) {
rotate_left( node );
ok = delete_node( node -> right_node, key );
} else {
rotate_right( node );
ok = delete_node( node -> left_node, key );
}
update_node( node );
}
return ok;
}
public:
nrx_treap() {
srand( time( NULL ) );
root = empty_node = new treap_node( 0, 0, INF, -INF, INF, NULL, NULL );
} // key, priority, min_dif, maxim, minim, left, right
int insert_node( int key ) {
return insert_node( root, key );
}
int delete_node( int key ) {
return delete_node( root, key );
}
int search_node( int key ) {
return search_node( root, key );
}
int max_difference() {
return root -> maxim - root -> minim;
}
int min_difference() {
return root -> min_difference;
}
int treap_size() {
return _treap_size;
}
} my_treap;
char S[DIM]; int N, X, ok;
int main() {
freopen( "zeap.in" , "r", stdin );
freopen( "zeap.out", "w", stdout );
while( scanf( "%s", S ) ) {
if( S[0] == 0 )
break;
switch( S[0] ) {
case 'I': {
scanf( "%d", &X );
ok = my_treap.insert_node( X );
break;
}
case 'S': {
scanf( "%d", &X );
ok = my_treap.delete_node( X );
if( ok == -1 )
printf( "-1\n" );
break;
}
case 'C': {
scanf( "%d", &X );
ok = my_treap.search_node( X );
if( ok == -1 )
printf( "0\n" );
else
printf( "1\n" );
break;
}
case 'M': {
if( S[1] == 'A' ) {
if( my_treap.treap_size() < 2 )
printf( "-1\n" );
else
printf( "%d\n", my_treap.max_difference() );
} else {
if( my_treap.treap_size() < 2 )
printf( "-1" );
else
printf( "%d\n", my_treap.min_difference() );
}
break;
}
}
S[0] = 0;
}
return 0;
}