#include <cstdio>
#include <algorithm>
#include <ctime>

using namespace std;

struct treap
{
    int val, pri, mi, ma, dmi;
    treap *le, *ri;

    treap ()
    {
        val = 0;
        pri = -1;
        mi = 1000000010;
        ma = 0;
        dmi = 1000000010;
        le = NULL;
        ri = NULL;
    }

    treap (int vv, int pp, int mini, int maxi, int difmi, treap *ll, treap *rr)
    {
        val = vv;
        pri = pp;
        mi = mini;
        ma = maxi;
        dmi = difmi;
        le = ll;
        ri = rr;
    }

} *root, *nul;

int ra ()
{
    return (rand () % 32000) * (rand () % 32000);
}

int aabs (int x)
{
    return max (x, -x);
}

void recount (treap *&nod)
{
    nod->mi = min (min (nod->le->mi, nod->ri->mi), nod->val);
    nod->ma = max (max (nod->le->ma, nod->ri->ma), nod->val);
    nod->dmi = min (min (nod->le->dmi, nod->ri->dmi), aabs (nod->val - nod->ri->mi));
    if (nod->le != nul) nod->dmi = min (nod->dmi, aabs (nod->val - nod->le->ma));
}

void roleft (treap *&nod)
{
    treap *aux;
    aux = nod->le;

    nod->le = aux->ri;
    aux->ri = nod;

    nod = aux;
    recount (nod->ri);
    recount (nod);
}

void roright (treap *&nod)
{
    treap *aux;
    aux = nod->ri;

    nod->ri = aux->le;
    aux->le = nod;

    nod = aux;
    recount (nod->le);
    recount (nod);
}

void balance (treap *&nod)
{
    if (nod->ri->pri > nod->pri) roright (nod);
    else if (nod->le->pri > nod->pri) roleft (nod);
}

void inserare (treap *&nod, int va, int p)
{
    if (nod->val == va) return;
    if (nod == nul)
    {
        nod = new treap (va, p, va, va, 1000000010, nul, nul);
        return;
    }

    if (va < nod->val) inserare (nod->le, va, p);
    else inserare (nod->ri, va, p);

    recount (nod);
    balance (nod);
}

int sterge (treap *&nod, int va)
{
    int ans;

    if (nod == nul) ans = 0;
    else if (nod->le == nul && nod->ri == nul)
    {
        if (nod -> val == va)
        {
            nod = nul;
            ans = 1;
        }

        else ans = 0;
    }

    else if (va < nod->val) ans = sterge (nod->le, va);
    else if (va > nod->val) ans = sterge (nod->ri, va);
    else
    {
        if (nod->le->pri > nod->ri->pri) roleft (nod);
        else roright (nod);
    }

    if (nod != nul) recount (nod);

    return ans;
}

int fin (treap *&nod, int va)
{
    if (nod->val == va) return 1;
    if (nod == nul) return 0;

    if (va < nod->val) return fin (nod->le, va);
    else return fin (nod->ri, va);
}

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

    srand (time (0));

    nul = new treap;
    root = nul;

    char op, aa;
    int va;
    scanf ("%c", &op);

    if (op == 'M') scanf ("%c", &aa), scanf ("%c", &aa);
    else scanf ("%d", &va);

    while (!feof (stdin))
    {
        if (op == 'I')
            inserare (root, va, ra ());

        else if (op == 'S')
        {
            if (!sterge (root, va)) printf ("-1\n");
        }

        else if (op == 'C')
            printf ("%d\n", fin (root, va));

        else if (aa == 'X')
        {
            if ((root->le != nul && root->le != NULL) || (root->ri != NULL && root->ri != nul)) printf ("%d\n", root->ma - root->mi);
            else printf ("-1\n");
        }

        else
        {
            if ((root->le != nul && root->le != NULL) || (root->ri != NULL && root->ri != nul)) printf ("%d\n", root->dmi);
            else printf ("-1\n");
        }


        scanf ("\n%c", &op);

        if (op == 'M') scanf ("%c", &aa), scanf ("%c", &aa);
        else scanf ("%d", &va);
    }

    return 0;
}