#include <bits/stdc++.h>

using namespace std;

ifstream f("zeap.in");
ofstream g("zeap.out");

const int inf=1e9;

bool ok;

struct T{
    int key,priority,_min,_max,_mindst;
    T *left,*right;
    T() {}
    T(int key,int priority,T* left,T* right){
        this->key=key;
        this->priority=priority;
        this->left=left,this->right=right;
        this->_min=key;
        this->_max=key;
        this->_mindst=1e9;
    }
} *R,*nil;

void upd(T* &n){
    if(n==nil)return ;
    int Lmin,Lmax,Lmindst,Rmin,Rmax,Rmindst;
    if(n->left!=nil){
        Lmin=n->left->_min;
        Lmax=n->left->_max;
        Lmindst=n->left->_mindst;
    }else{
        Lmin= 1e9;
        Lmax=-1e9;
        Lmindst=1e9;
    }
    if(n->right!=nil){
        Rmin=n->right->_min;
        Rmax=n->right->_max;
        Rmindst=n->right->_mindst;
    }else{
        Rmin= 1e9;
        Rmax=-1e9;
        Rmindst=1e9;
    }
    n->_min=min(n->key,min(Lmin,Rmin));
    n->_max=max(n->key,max(Lmax,Rmax));
    n->_mindst=min(min(n->key-Lmax,Rmin-n->key),min(Lmindst,Rmindst));
    return ;
}

int search(T* n,int key){
    if(n==nil)return 0;
    if(n->key==key)return 1;
    if(key<n->key)
        return search(n->left,key);
    return search(n->right,key);
}

void rotleft(T* &n){
    T *t=n->left;
    n->left=t->right,t->right=n;
    upd(n),upd(t);
    n=t;
}
void rotright(T* &n){
    T* t=n->right;
    n->right=t->left,t->left=n;
    upd(n),upd(t);
    n=t;
}
void balance(T* &n){
    if(n->left->priority>n->priority)
        rotleft(n);
    else if(n->right->priority>n->priority)
        rotright(n);
    upd(n->left);upd(n->right);upd(n);
}
void insert(T* &n,int key,int priority){
    if(n==nil){
        n=new T(key,priority,nil,nil);
        return ;
    }
    if(key<n->key)
        insert(n->left,key,priority);
    else if(key>n->key)
        insert(n->right,key,priority);
    balance(n);
}

void erase(T* &n,int key){
    if(n==nil)return ;
    if(n->key<key)
        erase(n->right,key);
    else if(n->key>key)
        erase(n->left,key);
    else{
        ok=1;
        if(n->left==nil&&n->right==nil){
            delete n,n=nil;
        }else{
            (n->left->priority>n->right->priority)?rotleft(n):rotright(n);
            erase(n,key);
        }
    }
    upd(n);
}
//pair<T*,T*> split(T* &n,int key){
//    insert(n,key,inf);
//    return {n->left,n->right};
//}
//void join(T* &R,T* lft,T *rgt,int key){
//    T* R=new T(key,0,lft,rgt);
//    erase(R,R->key);
//}


int main()
{
    srand(time(0));
    R=nil=new T(0,0,nil,nil);
    string c;int val,cnt=0;
    while(f>>c){
        if(c[0]=='I'){
            f>>val;cnt++;
            insert(R,val,rand()+1);
        }
        if(c[0]=='S'){
            ok=0;f>>val;
            erase(R,val);
            if(!ok)
                g<<-1<<'\n';
            else
                cnt--;
        }
        if(c[0]=='C'){
            f>>val;
            g<<search(R,val)<<'\n';
        }
        if(c[1]=='A'){
            if(cnt>=2)
                g<<(R->_max-R->_min)<<'\n';
            else
                g<<-1<<'\n';
        }
        if(c[1]=='I'){
            if(cnt>=2)
                g<<(R->_mindst)<<'\n';
            else
                g<<-1<<'\n';
        }
    }
    return 0;
}