#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 );
            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;
}