#include<fstream>
#include<time.h>
#include<stdlib.h>

using namespace std;

ifstream fi("zeap.in");
ofstream fo("zeap.out");

class node
{
    public:
        node *st,*dr;
        int val,pri,mx,mn,rez;

        node(node *x, node *y, int a, int b)
        {
            st=x;
            dr=y;
            val=mx=mn=a;
            pri=b;
            rez=1000000000;
        }
};

node *rad;

void compute(node *&nod)
{
    nod->mn=nod->mx=nod->val;
    nod->rez=1000000000;

    if(nod->st!=NULL)
    {
        nod->mn=min(nod->mn,nod->st->mn);
        nod->mx=max(nod->mx,nod->st->mx);

        nod->rez=nod->st->rez;
        nod->rez=min(nod->rez,(nod->val)-(nod->st->mx));
    }
    if(nod->dr!=NULL)
    {
        nod->mn=min(nod->mn,nod->dr->mn);
        nod->mx=max(nod->mx,nod->dr->mx);

        nod->rez=min(nod->rez,nod->dr->rez);
        nod->rez=min(nod->rez,(nod->dr->mn)-(nod->val));
    }
}

void toRight(node *&nod)
{
    node *aux=nod->st;
    nod->st=aux->dr;
    aux->dr=nod;

    compute(nod);
    compute(aux);

    nod=aux;
}

void toLeft(node *&nod)
{
    node *aux=nod->dr;
    nod->dr=aux->st;
    aux->st=nod;

    compute(nod);
    compute(aux);

    nod=aux;
}

void balance(node *&nod)
{
    if(nod->st!=NULL && (nod->st->pri)>(nod->pri))
        toRight(nod);
    if(nod->dr!=NULL && (nod->dr->pri)>(nod->pri))
        toLeft(nod);
}

void ins(node *&nod, int val, int pri)
{
    if(nod==NULL)
    {
        nod=new node(NULL,NULL,val,pri);
        return;
    }

    if(val<nod->val)
        ins(nod->st,val,pri);
    else if(val>nod->val)
        ins(nod->dr,val,pri);

    compute(nod);
    balance(nod);
}

int del(node *&nod, int val)
{
    if(nod==NULL)
        return 0;

    if(nod->val==val)
    {
        if(nod->st==NULL && nod->dr==NULL)
        {
            delete(nod);
            return 2;
        }

        if(nod->dr==NULL || (nod->st!=NULL && (nod->st->pri)>(nod->dr->pri)))
        {
            toRight(nod);

            int aux=del(nod->dr,val);

            if(aux==2)
                nod->dr=NULL;

            compute(nod);
            return (aux!=0);
        }
        else
        {
            toLeft(nod);

            int aux=del(nod->st,val);

            if(aux==2)
                nod->st=NULL;

            compute(nod);
            return (aux!=0);
        }
    }
    else if(val<nod->val)
    {
        int aux=del(nod->st,val);

        if(aux==2)
            nod->st=NULL;

        compute(nod);
        return (aux!=0);
    }
    else
    {
        int aux=del(nod->dr,val);

        if(aux==2)
            nod->dr=NULL;

        compute(nod);
        return (aux!=0);
    }
}

bool src(node *nod, int val)
{
    if(nod==NULL)
        return 0;

    if(val==nod->val)
        return 1;

    if(val<nod->val)
        return src(nod->st,val);
    else
        return src(nod->dr,val);
}

int main()
{
    srand(time(NULL));
    string S;
    while(fi>>S)
    {
        if(S=="I")
        {
            int x;
            fi>>x;

            ins(rad,x,1+rand());
        }
        else if(S=="S")
        {
            int x;
            fi>>x;

            if(!del(rad,x))
                fo<<"-1\n";
        }
        else if(S=="C")
        {
            int x;
            fi>>x;

            if(src(rad,x))
                fo<<"1\n";
            else
                fo<<"0\n";
        }
        else if(S=="MAX")
        {
            if(rad==NULL)
            {
                fo<<"-1\n";
                continue;
            }

            int rez=(rad->mx)-(rad->mn);
            if(rez==0)
                fo<<"-1\n";
            else
                fo<<rez<<"\n";
        }
        else
        {
            if(rad==NULL)
            {
                fo<<"-1\n";
                continue;
            }

            int rez=rad->rez;
            if(rez==1000000000)
                fo<<"-1\n";
            else
                fo<<rez<<"\n";
        }
    }
    fi.close();
    fo.close();
    return 0;
}