#include <fstream>
#include <iostream>
#include <stdlib.h>
#include <time.h>
#define INF 1000000000
using namespace std;
ifstream fin ("zeap.in");
ofstream fout("zeap.out");
int nr,ok,x;
char c[5];
struct T{
    int val;int heap;int mini;int maxi;int dif;
    T *st, *dr;
    T(){}
    T(int val, int heap, T *st, T *dr, int mini,int maxi ,int dif)
    {
        this->val=val;
        this->heap=heap;
        this->st=st;this->dr=dr;
        this->mini=mini;
        this->maxi=maxi;
        this->dif=dif;
    }
} *nod,*nil;
void show(T *nod, int level) {
    if(nod!=nil) {
        show(nod->dr, level+1);
        for(int i=1;i<=level;i++) cout<<"  ";
        cout<<nod->val<<" "<<nod->heap<<" "<<nod->mini<<" "<<nod->maxi<<" "<<nod->dif<<"\n";
        show(nod->st, level+1);
    }
}
void refresh(T *nod) {
    nod->mini=min(nod->val,min(nod->st->mini,nod->dr->mini));
    nod->maxi=max(nod->val,max(nod->st->maxi,nod->dr->maxi));
    nod->dif=min(nod->val-nod->st->maxi,min(nod->dr->mini-nod->val,min(nod->st->dif,nod->dr->dif)));
}
void turnright(T *&nod) {
    T *t=nod->st;
    nod->st=t->dr;t->dr=nod;
    nod=t;
    refresh(nod->dr);
    refresh(nod);
}
void turnleft(T* &nod) {
    T *t=nod->dr;
    nod->dr=t->st;t->st=nod;
    nod=t;
    refresh(nod->st);
    refresh(nod);
}
void balance(T* &nod) {
    if(nod->st!=NULL&&nod->st->heap>nod->heap) turnright(nod);
    else if(nod->dr!=NULL&&nod->dr->heap>nod->heap) turnleft(nod);
}
void in(T *&nod,int val,int heap)
{
    if(nod==nil)
    {
        nod=new T(val,heap,nil,nil,val,val,INF);nr++;
        return;
    }
    if(val<nod->val) in(nod->st,val,heap);
    else if(val>nod->val) in(nod->dr,val,heap);
    balance(nod);
    refresh(nod);
}
void out(T *&nod,int val)
{
    if(nod==nil) return;
    if(val<nod->val) out(nod->st,val);
    else if(val>nod->val) out(nod->dr,val);
    else if(val==nod->val)
    {
        if(nod->st==nil&&nod->dr==nil)
        {
            delete nod;
            nod=nil,ok=1,nr--;
        }
        else
        {
            if(nod->st->heap>nod->dr->heap) turnright(nod);
            else turnleft(nod);
            out(nod,val);
        }
    }
    if(nod!=nil) refresh(nod);
}
int cauta(T *&nod, int val)
{
    if(nod==nil) return 0;
    if(nod->val==val) return 1;
    if(nod->val>val) return cauta(nod->st,val);
    return cauta(nod->dr,val);
}
int main ()
{
    srand(time(0));int op=10;
    nod=nil=new T(0, 0, NULL, NULL, INF, -INF, INF);
    while(fin>>c)
    {
        //show(nod,0);cout<<"\n";
        if(c[0]=='I')
        {
            fin>>x;in(nod,x,rand());
            continue;
        }
        if(c[0]=='S')
        {
            fin>>x;
            ok=0;out(nod,x);
            if(ok==0) fout<<"-1\n";
            continue;
        }
        if(c[0]=='C')
        {
            fin>>x;fout<<cauta(nod,x)<<"\n";
            continue;
        }
        if(c[1]=='I')
        {
            if(nr>=2) fout<<nod->dif<<"\n"; else fout<<"-1\n";
            continue;
        }
        if(nr>=2) fout<<nod->maxi-nod->mini<<"\n"; else fout<<"-1\n";
    }
    return 0;
}