#include <fstream>
#include <cstdlib>
#include <ctime>

using namespace std;

ifstream f("zeap.in");
ofstream g("zeap.out");

const int INF=0x3f3f3f3f3f;

struct treap
{
    int key, priority, minv, maxv, mindif, maxdif;
    treap *left, *right;

    treap (int key, int priority, int minv, int maxv, int mindif, int maxdif, treap* left, treap *right)
    {
        this->key=key;
        this->priority=priority;
        this->minv=minv;
        this->maxv=maxv;
        this->mindif=mindif;
        this->maxdif=maxdif;
        this->left=left;
        this->right=right;
    }
} *root, *nil;

void initialize ()
{
    srand(time(0));

    root=nil=new treap(0, 0, INF, -INF, INF, -INF, NULL, NULL);
}

bool search (treap* &node, int key)
{
    if (node==nil)
        return 0;
    if (node->key==key)
        return 1;

    if (key < node->key)
        return search(node->left, key);

    return search(node->right, key);
}

void update (treap* &node)
{
    node->maxv=max(node->key, max(node->left->maxv, node->right->maxv));
    node->minv=min(node->key, min(node->left->minv, node->right->minv));

    node->mindif=min(node->left->mindif, node->right->mindif);
    node->maxdif=min(node->right->maxdif, node->right->maxdif);

    node->mindif=min(node->mindif, min(node->right->minv - node->key, node->key - node->right->maxv));
    node->maxdif=max(node->maxdif, node->maxv - node->minv);
}

void rotate_right (treap* &node)
{
    treap *aux=node->left;
    node->left=aux->right;
    aux->right=node;
    node=aux;

    update(node);
    update(node->right);
}

void rotate_left (treap* &node)
{
    treap *aux=node->right;
    node->right=aux->left;
    aux->left=node;
    node=aux;

    update(node);
    update(node->right);
}

void balance (treap* &node)
{
    if (node->left->priority > node->priority)
        rotate_right(node);

    if (node->right->priority > node->priority)
        rotate_left(node);
}

void insert (treap* &node, int key, int priority)
{
    if (node==nil)
    {
        node=new treap(key, priority, key, key, INF, -INF, nil, nil);
        return;
    }

    if (key < node->key)
        insert(node->left, key, priority);
    else
        insert(node->right, key, priority);

    balance(node);
    update(node);
}

void erase (treap* &node, int key)
{
    if (node==nil)
        return;

    if (node->key==key)
    {
        if (node->left==nil && node->right==nil)
        {
            delete node;
            node=nil;
            return;
        }

        if (node->left->priority > node->right->priority)
        {
            rotate_right(node);
            erase(node->right, key);
        }
        else
        {
            rotate_left(node);
            erase(node->left, key);
        }
    }
    else
    {
        if (key < node->key)
            erase(node->left, key);
        else
            erase(node->right, key);
    }

    update(node);
}

int main ()
{
    initialize();

    string op;
    int x;

    while (f >> op)
    {
        if (op.size()==1)
        {
            f >> x;
            bool found=search(root, x);

            if (op=="I")
            {
                if (found==0)
                    insert(root, x, rand());
            }
            if (op=="C")
                g << found << '\n';
            if (op=="S")
            {
                if (found==0)
                    g << -1 << '\n';
                else
                    erase(root, x);
            }
        }
        else
        {
            if (op=="MAX")
                g << (root->maxdif>-INF?root->maxdif:-1) << '\n';
            else
                g << (root->mindif<INF?root->mindif:-1) << '\n';
        }
    }

    f.close();
    g.close();

    return 0;
}