#include <algorithm>
#include <fstream>
#include <cstdlib>
#include <string>
#include <ctime>

using namespace std;

const int INF=0x3f3f3f3f;

struct Treap {
    int key, pry, minval, maxval, mindiff, maxdiff;
    Treap *left, *right;
    Treap() {}
    Treap(int _key, int _pry, Treap *_left, Treap *_right, int _minval, int _maxval, int _mindiff, int _maxdiff)
    {
        key=_key;
        pry=_pry;
        left=_left;
        right=_right;
        minval=_minval;
        maxval=_maxval;
        mindiff=_mindiff;
        maxdiff=_maxdiff;
    }
};

Treap *Root, *NIL;

void Init()
{
    srand(unsigned(time(0)));
    Root=NIL=new Treap(0, 0, NULL, NULL, INF, -INF, INF, -INF);
    NIL->left=NIL->right=NIL;
}



void GetVals(Treap* &node)
{
    node->minval=min(node->key, min(node->left->minval, node->right->minval));
    node->maxval=max(node->key, max(node->left->maxval, node->right->maxval));

    node->mindiff=min(min(node->left->mindiff, node->right->mindiff), min(node->key-node->left->maxval, node->right->minval-node->key));
    node->maxdiff=max(max(node->left->maxdiff, node->right->maxdiff), node->maxval-node->minval);
}

void RotLeft(Treap* &node)
{
    Treap *t=node->left;
    node->left=t->right;
    t->right=node;
    node=t;

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

void RotRight(Treap* &node)
{
    Treap *t=node->right;
    node->right=t->left;
    t->left=node;
    node=t;

    GetVals(node->left);
    GetVals(node);
}

void Balance(Treap* &node)
{
    if(node->left->pry>node->pry) RotLeft(node);
    if(node->right->pry>node->pry) RotRight(node);
}

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

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

void Insert(Treap* &node, int key, int pry)
{
    if(node==NIL)
    {
        node=new Treap(key, pry, NIL, NIL, key, key, INF, -INF);
        return;
    }

    if(key<node->key) Insert(node->left, key, pry);
    else Insert(node->right, key, pry);

    Balance(node);
    GetVals(node);
}

bool Erase(Treap* &node, int key)
{
    if(node==NIL) return 0;

    int ret;
    if(key==node->key)
    {
        ret=1;
        if(node->left==NIL&&node->right==NIL)
        {
            delete node;
            node=NIL;
            return 1;
        }
        if(node->left->pry>node->right->pry)
        {
            RotLeft(node);
            Erase(node->right, key);
        }
        else
        {
            RotRight(node);
            Erase(node->left, key);
        }
    }
    else
    {
        if(key<node->key) ret=Erase(node->left, key);
        else if(key>node->key) ret=Erase(node->right, key);
    }

    GetVals(node);
    return ret;
}

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

    int N;
    string op;

    Init();

    while(fin>>op)
    {
        if(op=="C")
        {
            fin>>N;
            fout<<Find(Root, N)<<"\n";
        }
        else if(op=="I")
        {
            fin>>N;
            Insert(Root, N, rand()+1);
        }
        else if(op=="S")
        {
            fin>>N;
            if(!Erase(Root, N)) fout<<"-1\n";
        }
        else if(op=="MAX")
        {
            fout<<(Root->maxdiff>-INF?Root->maxdiff:-1)<<"\n";
        }
        else
        {
            fout<<(Root->mindiff<INF?Root->mindiff:-1)<<"\n";
        }
    }

    fin.close();
    fout.close();
}