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

#define INF 0x3f3f3f3f
int marime;
using namespace std;
class Treap{
public:
    Treap *st,*dr;
    int value,priority;
    int mindiff,maxdiff;
    int mini,maxi;
    Treap(){
        this->st = NULL;
        this->dr = NULL;
        this->value = 0;
        this->priority = 0;
        this-> mini = INF;
        this-> maxi = -INF;
        this-> mindiff = INF;
        this-> maxdiff = -INF;
        mindiff = maxdiff= mini = maxi = 0;
    }
    Treap(int value,int priority,Treap *st,Treap *dr){
        this->value = value;
        this->priority = priority;
        this->st = st;
        this->dr = dr;
        this-> mini = INF;
        this-> maxi = -INF;
        this-> mindiff = INF;
        this-> maxdiff = -INF;
    }
}*root,*nil;
void init(){
    srand(unsigned(time(0) + 1));
    root = nil = new Treap(0,0,NULL,NULL);
}

void Rotate_left(Treap *&T)
{
    Treap *aux = T->st;
    T->st = aux->dr;
    aux->dr = T;
    T = aux;
}
void Rotate_right(Treap *&T)
{
    Treap *aux = T->dr;
    T->dr = aux->st;
    aux->st = T;
    T = aux;
}
void Balance(Treap *&T)
{
    if(T->st->priority > T->priority)
        Rotate_left(T);
    else
        if(T->dr->priority > T->priority)
            Rotate_right(T);
}
void Insert(int value,int priority,Treap *&T)
{
    if( T == nil){
        ++marime;
        T = new Treap(value,priority,nil,nil);
        return;
    }
    if(T->value == value) return; ///ignor
    if(T->value > value)
        Insert(value,priority,T->st);
    else
        Insert(value,priority,T->dr);
    Balance(T);
}
int Search(int value,Treap *T)
{
    if(T == nil) return 0;
    if(T->value == value) return 1;
    if(T->value > value)
        return Search(value, T->st);
    return Search(value, T->dr);
}
void Delete(int value,Treap *&T)
{
    if(T == nil){
        printf("-1\n");
        return;
    }
    if(T->value > value)
        Delete(value,T->st);
    else
        if(T->value < value)
            Delete(value,T->dr);
        else
            if(T->st == nil && T->dr == nil){ delete T; T = nil; --marime;return;}
            else
            {
                if(T->st->priority > T->dr->priority)   Rotate_left(T);
                else    Rotate_right(T);
                Delete(value,T);
            }
}
void Update(Treap *&T)
{
    if(T == nil) return;

    Update(T->st);
    Update(T->dr);

    T->mini = min(T->value,min(T->st->mini,T->dr->mini));
    T->maxi = max(T->value,max(T->st->maxi,T->dr->maxi));
    if(T->st == nil && T->dr == nil)
        return;
    if(T->st != nil && T->dr != nil)
    {
        T->maxdiff = T->dr->maxi - T->st->mini;
        T->mindiff = min(T->value - T->st->maxi , T->dr->mini - T->value);
        T->mindiff = min(T->mindiff,min(T->st->mindiff,T->dr->mindiff));
    }
    if(T->st == nil)
    {
        T->maxdiff = T->maxi - T->value;
        T->mindiff = T->dr->mini - T->value;
    }
    if(T->dr == nil)
    {
        T->maxdiff = T->value - T->mini;
        T->mindiff = T->value - T->st->maxi;
    }

}

void Maxdiff(Treap *&T){
    if(marime < 2)
    {
        printf("-1\n");
        return;
    }
    Update(T);
    int vl = T->maxdiff;
    printf("%d\n",vl);
}
void Mindiff(Treap *&T){
    if(marime < 2)
    {
        printf("-1\n");
        return;
    }
    Update(T);
    int vl = T->mindiff;
    printf("%d\n",vl);
}

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

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

    return 0;
}