#include <cstdio>
#include <cstdlib>
#include <time.h>
#include <algorithm>
#include <cstring>

#define INF 0x3f3f3f3f

using namespace std;

char op[10];
int x,Size;


class Treap{
public:
    Treap *st,*dr;
    int value,priority;
    int minim,maxim;
    int mindiff,maxdiff;
    Treap(){
        st = dr = NULL;
        value = priority = 0;
        minim = maxim = 0;
        mindiff = maxdiff = 0;
    }
    Treap(int value,int priority,int minim,int maxim,int mindiff,int maxdiff,Treap *st,Treap *dr){
        this->value = value;
        this->priority = priority;
        this->minim = minim;
        this->maxim = maxim;
        this->mindiff = mindiff;
        this->maxdiff = maxdiff;
        this->st = st;
        this->dr = dr;
    }
}*root,*nil;

void init(){
    srand(unsigned(time(0)));
    root = nil = new Treap(0,0,INF,-INF,INF,-INF,NULL,NULL);
}

void Rotate_left(Treap *&T)
{
    Treap *aux = T->st;

    aux->minim = min(aux->minim,T->minim);
    aux->maxim = max(aux->maxim,T->maxim);

    T->st = aux->dr;

    T->minim = T->value;
    T->maxim = T->value;

    if(T->st != nil){
            T->minim = min(T->minim,T->st->minim);
            T->maxim = max(T->maxim,T->st->maxim);
    }
    if(T->dr != nil){
            T->minim = min(T->minim,T->dr->minim);
            T->maxim = max(T->maxim,T->dr->maxim);
    }

    aux->dr = T;
    T = aux;

    T->maxdiff = max(T->st->maxdiff,T->dr->maxdiff);
    T->maxdiff = max(T->maxdiff,max(T->value - T->st->minim, T->dr->maxim - T->value));

    T->mindiff = min(T->st->mindiff,T->dr->mindiff);
    T->mindiff = min(T->mindiff,min(T->value - T->st->maxim, T->dr->minim - T->value));


    aux->maxdiff = max(aux->st->maxdiff,aux->dr->maxdiff);
    aux->maxdiff = max(aux->maxdiff,max(aux->value - aux->st->minim, aux->dr->maxim - aux->value));

    aux->mindiff = min(aux->st->mindiff,aux->dr->mindiff);
    aux->mindiff = min(aux->mindiff,min(aux->value - aux->st->maxim, aux->dr->minim - aux->value));


}
void Rotate_right(Treap *&T)
{
    Treap *aux = T->dr;

    aux->minim = min(aux->minim,T->minim);
    aux->maxim = max(aux->maxim,T->maxim);

    T->dr = aux->st;

    if(T->st != nil){
            T->minim = min(T->minim,T->st->minim);
            T->maxim = max(T->maxim,T->st->maxim);
    }
    if(T->dr != nil){
            T->minim = min(T->minim,T->dr->minim);
            T->maxim = max(T->maxim,T->dr->maxim);
    }

    aux->st = T;
    T = aux;

    T->maxdiff = max(T->st->maxdiff,T->dr->maxdiff);
    T->maxdiff = max(T->maxdiff,max(T->value - T->st->minim, T->dr->maxim - T->value));

    T->mindiff = min(T->st->mindiff,T->dr->mindiff);
    T->mindiff = min(T->mindiff,min(T->value - T->st->maxim, T->dr->minim - T->value));


    aux->maxdiff = max(aux->st->maxdiff,aux->dr->maxdiff);
    aux->maxdiff = max(aux->maxdiff,max(aux->value - aux->st->minim, aux->dr->maxim - aux->value));

    aux->mindiff = min(aux->st->mindiff,aux->dr->mindiff);
    aux->mindiff = min(aux->mindiff,min(aux->value - aux->st->maxim, aux->dr->minim - aux->value));
}

void Balance(Treap *&T)
{
    if(T->st->priority > T->priority)
        Rotate_left(T);
    else
        if(T->dr->priority > T->priority)
            Rotate_right(T);

    T->maxdiff = max(T->st->maxdiff,T->dr->maxdiff);
    T->maxdiff = max(T->maxdiff,max(T->value - T->st->minim, T->dr->maxim - T->value));

    T->mindiff = min(T->st->mindiff,T->dr->mindiff);
    T->mindiff = min(T->mindiff,min(T->value - T->st->maxim, T->dr->minim - T->value));
}


void Insert(int value,int priority,Treap *&T)
{
    if(T == nil){
        ++Size;
        T = new Treap(value,priority,value,value,INF,-INF,nil,nil);
        return;
    }
    if(T->value > value)
        Insert(value,priority,T->st);
    else
        if(T->value < value)
            Insert(value,priority,T->dr);
        else
            return;
    Balance(T);
}
void Sterge(int value,Treap *&T)
{
    if(T == nil){
        printf("-1\n");
        return;
    }
    if(T->value > value)
        Sterge(value,T->st);
    else
        if(T->value < value)
            Sterge(value,T->dr);
        else
            if(T->st == nil && T->dr == nil)
            {
                delete T,T = nil;
                --Size;
                return;
            }
            else
            {
                if(T->st->priority > T->dr->priority)
                    Rotate_left(T);
                else
                    Rotate_right(T);
                Sterge(value,T);
            }


    T->maxdiff = -INF;
    T->mindiff =  INF;
    T->maxdiff = max(T->st->maxdiff,T->dr->maxdiff);
    T->maxdiff = max(T->maxdiff,max(T->value - T->st->minim, T->dr->maxim - T->value));

    T->mindiff = min(T->st->mindiff,T->dr->mindiff);
    T->mindiff = min(T->mindiff,min(T->value - T->st->maxim, T->dr->minim - T->value));
}

void Search(int value,Treap *T)
{
    if(T == nil)
    {
        printf("0\n");
        return;
    }
    if(T->value  == value)
    {
        printf("1\n");
        return;
    }
    if(T->value > value)
        Search(value,T->st);
    else
        Search(value,T->dr);
}
void Maxdiff(Treap *T)
{
    if(Size >= 2)
        printf("%d\n",T->maxdiff);
    else
        printf("-1\n");
}
void Mindiff(Treap *T)
{
    if(Size >= 2)
        printf("%d\n",T->mindiff);
    else
        printf("-1\n");
}

void afish( Treap *T)
{
    if(T == nil) return;
    afish(T->st);
    printf("%d ",T->value);
    afish(T->dr);
}

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

    init();
    while(scanf("%s",op) != -1)
    {
        if(op[0] == 'I')
        {
            scanf("%d",&x);
            Insert(x,rand()+1,root);
            ///afish(root);
            ///printf("\n");
        }
        if(op[0] == 'S')
        {
            scanf("%d",&x);
            Sterge(x,root);
            ///afish(root);
            ///printf("\n");
        }
        if(op[0] == 'C')
        {
            scanf("%d",&x);
            Search(x,root);
        }
        if(op[1] == 'A')
            Maxdiff(root);
        if(op[1] == 'I')
            Mindiff(root);
        memset(op,0,sizeof(op));
    }

    return 0;
}