#include <bits/stdc++.h>

#define INF 2000000000

using namespace std;


ifstream fin("zeap.in");
ofstream fout("zeap.out");

int treapSize;
bool amSters;
string type;

struct T{
    int key;
    int priority;
    int maxim;
    int minim;
    int dif_min;
    T *left;
    T *right;
    T(){};
    T(int key, int priority, int maxim, int minim, int dif_min, T *left, T *right)
    {
        this -> key = key;
        this -> priority = priority;
        this -> left = left;
        this -> right = right;
        this -> minim = minim;
        this -> maxim = maxim;
        this -> dif_min = dif_min;
    }

} *Root, *NIL; // nod gol

void init() {
    srand(unsigned(time(0)));
    Root = NIL = new T(0, 0, -INF, INF, INF, NULL, NULL);
}

inline void update(T* & node)
{
    node -> minim = min(node -> left -> minim, node -> key);
    node -> maxim = max(node -> right -> maxim, node -> key);
    node -> dif_min = min( min((long long)node -> left -> dif_min, (long long)node -> right -> dif_min),
                           min( (long long)node -> key - (long long)node -> left -> maxim, (long long)node -> right -> minim -(long long) node -> key) );
}

inline void rotateRight(T* &node)
{
    T *tmp = node -> left;
    node -> left = tmp -> right;
    tmp -> right = node;
    node = tmp;
    update(node -> right);
    update(node);
}

inline void rotateLeft(T* &node)
{
    T *tmp = node -> right;
    node -> right = tmp -> left;
    tmp -> left = node;
    node = tmp;
    update(node -> left);
    update(node);
}
inline void balance(T* &node)
{
    if(node -> left -> priority > node -> priority)
    {
        rotateRight(node);
    }
    else if(node -> right -> priority > node -> priority)
        {
            rotateLeft(node);
        }
}

inline void insert(T* &node, const int &value, const int &priority)
{
    int leftN = 0, rightN = 0;
    if(node == NIL)
    {
        node = new T(value, priority, value, value, INF, NIL, NIL);
        treapSize ++;
        return;
    }
    if(node -> key > value)
    {
        insert(node -> left, value, priority);

    }
    else if(node -> key < value)
         {
             insert(node -> right, value, priority);
         }

    balance(node);
    update(node);
}

inline int search(T* &node, const int &value)
{
    if(node == NIL)
    {
        return 0;
    }

    if(node -> key == value)
    {
        return 1;
    }

    if(node -> key > value)
    {
        search(node -> left, value);
    }
    else
    {
        search(node -> right, value);
    }
}

inline void erase(T* &node, const int &value)
{
    if(node == NIL)
    {
        return;
    }
    if(node -> key > value)
    {
        erase(node -> left, value);
    }
    else if(node -> key < value)
         {
            erase(node -> right, value);
         }
         else
         {
             if(node -> left == NIL && node -> right == NIL) // e frunza
             {
                 amSters = true;
                 delete node;
                 node = NIL;
                 treapSize --;
             }
             else
             {
                 if(node -> left -> priority > node -> right -> priority)
                 {
                     rotateRight(node);
                 }
                 else
                 {
                     rotateLeft(node);
                 }
                 erase(node, value);
             }
         }
         if(node != NIL)
            update(node);
}

int main()
{
    init();
    int i = 0;
    while(fin >> type)
    {
        i ++;
        if(type == "I")
        {
            int x; fin >> x;
            insert(Root, x, rand() + 1);
        }
        if(type == "S")
        {
            amSters = false;
            int x; fin >> x;
            erase(Root, x);
            if(amSters == false)
            {
                fout << "-1\n";
            }
        }
        if(type == "C")
        {
            int x; fin >> x;
            fout << search(Root, x) << '\n';
        }
        if(type == "MAX")
        {
            if(treapSize < 2)
            {
                fout << "-1\n";
                continue;
            }
            fout << Root -> maxim - Root -> minim << '\n';
        }
        if(type == "MIN")
        {
            if(treapSize < 2)
            {
                fout << "-1\n";
                continue;
            }
            fout << Root -> dif_min << '\n';
        }

    }

    return 0;
}