#include <fstream>
#include <iostream>
#include <string>
#include <sstream>

using namespace std;

struct cel
{
    int minim,maxim,val,lung,grad,difmin;
    cel *st,*dr;
    cel() { st=0; dr=0; }
};

typedef cel *arbech;

arbech arb;

int x;

string s,st;

int cauta(arbech nod,int x)
{
    if (nod==0) return 0;
    else
    {
        if (nod->val>x)
        {
            return cauta(nod->st,x);
        }else
        if (nod->val<x)
        {
            return cauta(nod->dr,x);
        }else if (nod->val==x) return 1;
    }
}

arbech calcgrad(arbech nod)
{
    if (nod==0) return 0;
    if (nod->st==0 && nod->dr==0)
    {
        nod->grad=0;
        nod->lung=1;
    }else if (nod->st==0)
    {
        nod->grad=nod->dr->lung;
        nod->lung=nod->dr->lung+1;
    }else if (nod->dr==0)
    {
        nod->grad=-nod->st->lung;
        nod->lung=nod->st->lung+1;
    }else
    {
        nod->lung=nod->dr->lung;
        if (nod->lung<nod->st->lung) nod->lung=nod->st->lung;
        nod->lung++;
        nod->grad=nod->dr->lung-nod->st->lung;
    }
    return nod;
}

arbech calcparam(arbech nod)
{
    if (nod==0) return 0;
    if (nod->st==0 && nod->dr==0)
    {
        nod->minim=nod->val;
        nod->maxim=nod->val;
        nod->difmin=2000000000;
    }else if (nod->st==0)
    {
        nod->minim=nod->val;
        nod->maxim=nod->dr->maxim;
        nod->difmin=nod->dr->minim-nod->val; if (nod->dr->difmin<nod->difmin) nod->difmin=nod->dr->difmin;
    }else if (nod->dr==0)
    {
        nod->minim=nod->st->minim;
        nod->maxim=nod->val;
        nod->difmin=nod->val-nod->st->maxim; if (nod->st->difmin<nod->difmin) nod->difmin=nod->st->difmin;
    }else
    {
        nod->minim=nod->st->minim;
        nod->maxim=nod->dr->maxim;
        nod->difmin=nod->dr->minim-nod->val;
        if (nod->dr->difmin<nod->difmin) nod->difmin=nod->dr->difmin;
        if (nod->st->difmin<nod->difmin) nod->difmin=nod->st->difmin;
        if (nod->val-nod->st->maxim<nod->difmin) nod->difmin=nod->val-nod->st->maxim;
    }
    return nod;
}

arbech rotestedr(arbech nod)
{
    if (nod==0) return 0;
    arbech p=nod->st;
    nod->st=p->dr;
    p->dr=nod;
    nod=calcgrad(nod);
    nod=calcparam(nod);
    p=calcgrad(p);
    p=calcparam(p);
    return p;
}

arbech rotestest (arbech nod)
{
    if (nod==0) return 0;
    arbech p=nod->dr;
    nod->dr=p->st;
    p->st=nod;
    nod=calcgrad(nod);
    nod=calcparam(nod);
    p=calcgrad(p);
    p=calcparam(p);
    return p;
}

arbech balanseaza(arbech nod)
{
    if (nod==0) return 0;
    nod=calcgrad(nod);
    nod=calcparam(nod);
    if (nod->grad==-2)
    {
        if (nod->st->grad<=0) nod=rotestedr(nod); else { nod->st=rotestest(nod->st); nod=rotestedr(nod); }
    }else if (nod->grad==2)
    {
        if (nod->dr->grad>=0) nod=rotestest(nod); else { nod->dr=rotestedr(nod->dr); nod=rotestest(nod); }
    }
    return nod;
}

arbech inserez(arbech nod,int x)
{
    if (nod==0)
    {
        arbech p=new cel;
        p->dr=0;
        p->st=0;
        p->val=x;
        p->grad=0;
        p->lung=1;
        p->maxim=x;
        p->minim=x;
        p->difmin=2000000000;
        return p;
    }

    if (x>nod->val)
    {
        nod->dr=inserez(nod->dr,x);
        return balanseaza(nod);
    }else
    if (x<nod->val)
    {
        nod->st=inserez(nod->st,x);
        return balanseaza(nod);
    }
    return nod;
}

arbech sterge(arbech nod,int x)
{
    if (nod==0) return 0;
    if (x==nod->val)
    {
        if (nod->st==0 && nod->dr==0) return 0;
        else if (nod->st==0 && nod->dr!=0) return nod->dr;
        else if (nod->st!=0 && nod->dr==0) return nod->st;

        arbech p=nod->dr;
        while (p->st!=0) p=p->st;
        nod->val=p->val;
        nod->dr=sterge(nod->dr,nod->val);
        return balanseaza(nod);
    }else
        if (x>nod->val) nod->dr=sterge(nod->dr,x);
        else    nod->st=sterge(nod->st,x);


    return balanseaza(nod);
}

int main ()
{
    ifstream in ("zeap.in");
    ofstream out ("zeap.out");
    getline(in,s,char(EOF));
    stringstream cin;
    cin<<s;
    arb=0;
    while (cin>>st)
    {
        if (st[0]=='I')
        {
            cin>>x;
            arb=inserez(arb,x);

        }else if (st[0]=='S')
        {
            cin>>x;
            int v=cauta(arb,x);
            if (v==0) out<<"-1\n"; else arb=sterge(arb,x);
        }else if (st[0]=='C')
        {
           cin>>x;
           out<<cauta(arb,x)<<"\n";
        }else
        {
            if (st=="MIN")
                {
                    if(arb!=0) { if (arb->st!=0 || arb->dr!=0) out<<arb->difmin<<"\n";else out<<"-1\n";} else out<<"-1\n";
                }else
                {
                    if (arb!=0) { if (arb->st!=0 || arb->dr!=0) out<<arb->maxim-arb->minim<<"\n";else out<<"-1\n"; }else out<<"-1\n";
                }
        }
        getline(cin,st);
    }
    in.close();
    out.close();
    return 0;
}