#include <iostream>
#include <ctime>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#define INFINIT 0x3f3f3f3f
using namespace std;

struct Treap
{
    int key, priority;
    Treap *left, *right;

    Treap(int key, int priority, Treap *left, Treap *right)
    {
        this->key = key;
        this->priority = priority;
        this->left = left;
        this->right = right;
    }
}*root,*NIL;

bool treapSearch(Treap *node, int key)
{
    if(node == NIL)
        return 0;
    if(node->key == key)
        return 1;

    if(key < node->key)
        return treapSearch(node->left,key);
    return treapSearch(node->right,key);
}

void rotateLeft(Treap* &node)
{
    Treap *aux = node->left;
    node->left = aux->right;
    aux->right = node;
    node = aux;
}

void rotateRight(Treap* &node)
{
    Treap *aux = node->right;
    node->right = aux->left;
    aux->left = node;
    node = aux;
}

void balance(Treap* &node)
{
    if(node->left->priority > node->priority)
        rotateLeft(node);
    else if(node->right->priority > node->priority)
        rotateRight(node);
}

void treapInsert(Treap* &node,int key)
{
    if(node == NIL)
    {
        node = new Treap(key,rand()+1,NIL,NIL);
        return;
    }
    if(key < node->key)
        treapInsert(node->left,key);
    else treapInsert(node->right,key);

    balance(node);
}

bool treapRemove(Treap* &node,int key)
{
    if(node == NIL)
        return false;
    if(key < node->key)
    {
        return treapRemove(node->left, key);
    }
    else if( key > node->key)
    {
        return treapRemove(node->right, key);
    }
    else
    {
        if(node->left == NIL && node->right == NIL)
        {
            delete node;
            node = NIL;
            return true;
        }
        else
        {
            if(node->left->priority > node->right->priority)
            {
                rotateLeft(node);
            }
            else
            {
                rotateRight(node);
            }
            return treapRemove(node,key);
        }
    }
}

int treapMax(Treap* node)
{
    if(node->right == NIL)
        return node->key;
    return treapMax(node->right);
}

int treapMin(Treap *node)
{
    if(node->left == NIL)
        return node->key;
    return treapMin(node->left);
}

int treapMinDiff(Treap *node,int k)
{
    if(node->left == NIL && node->right == NIL)
        return INFINIT;
    int dleft = (node->left != NIL) ? abs(node->key - node->left->key) : INFINIT;
    int dright = (node->right != NIL) ? abs(node->key - node->right->key) : INFINIT;

    return min(k,min(dleft,dright));
}

char line[100];

int next_int()
{
    int i = 0, x = 0;
    for(;line[i]!=' ';i++);
    i++;
    while(line[i]!='\n')
    {
        x = x * 10 + line[i]-'0';
        i++;
    }
    return x;
}

int main()
{
    srand(time(0));
    root = NIL = new Treap(0,0,0,0);

    freopen("zeap.in","r",stdin);
    freopen("zeap.out","w",stdout);

    while(fgets(line,100,stdin))
    {
        if(line[0]=='I')
        {
            int key = next_int();
            treapInsert(root,key);
        }
        else if(line[0]=='S')
        {
            int key = next_int();
            int ok = treapRemove(root,key);
            if(!ok)
                printf("%d\n",-1);
        }
        else if(line[0]=='C')
        {
            int key = next_int();
            printf("%d\n",treapSearch(root,key));
        }
        else if(line[0]=='M' && line[1]=='A')
        {
            printf("%d\n",abs(treapMax(root)-treapMin(root)));
        }
        else if(line[0]=='M' && line[1]=='I')
        {
            printf("%d\n",treapMinDiff(root,INFINIT));
        }
    }
    return 0;
}