#include <stdio.h>     
#include <algorithm>     
#include <time.h>     
#define max_pon 48234383     
#define ms 1000000001     
     
using namespace std;     
     
struct treap     
{     
    int key, prty, min, max, difm;     
    treap *l, *r;     
    treap(int key, int prty, int min, int max, int difm, treap *r, treap *l)     
    {     
        this->key = key, this->prty = prty, this->min = min, this->max = max;     
        this->difm = difm, this->r = r, this->l = l;     
    }     
} *rad_tr, *nil;     
     
int x, ct;     
char oper, op2;     
     
void calc(treap* &n)     
{     
    n->min = min(n->key, n->l->min), n->max = max(n->key, n->r->max);     
    n->difm = min(min(n->r->difm, n->l->difm), min(n->r->min - n->key, n->key - n->l->max));     
}     
     
void rr(treap* &n)     
{     
    treap *t = n->r;     
    n->r = t->l, t->l = n;     
    n = t;     
    if (n != nil && n->l != nil)     
        calc(n->l);     
}     
     
void rl(treap* &n)     
{     
    treap *t = n->l;     
    n->l = t->r, t->r = n;     
    n = t;     
    if (n != nil && n->r != nil)     
        calc(n->r);     
}     
     
void balance(treap* &n)     
{     
    if (n->r->prty > n->prty)     
        rr(n);     
    else if (n->l->prty > n->prty)     
        rl(n);     
    calc(n);     
}     
     
void insert_tr(treap* &n, int key, int pr)     
{     
    if (n == nil)     
    {     
        n = new treap(key, pr, key, key, ms, nil, nil);     
        return;     
    }     
    if (key > n->key)     
        insert_tr(n->r, key, pr);     
    else if (key < n->key)     
        insert_tr(n->l, key, pr);     
    balance(n);     
}     
     
void erase_tr(treap* &n, int key)     
{     
    if (n == nil)     
        return;     
    if (n->key > key)     
        erase_tr(n->l, key);     
    else if (n->key < key)     
        erase_tr(n->r, key);     
    else     
    {     
        if (n->l->prty > n->r->prty)     
            rl(n);     
        else rr(n);     
        if (n != nil)     
            erase_tr(n, key);     
        else     
        {     
            delete n->l;     
            n->l = NULL;     
            return;     
        }     
    }     
    calc(n);     
}     
    
int cauta_tr(treap *n, int key)     
{     
    if (n == nil)     
        return 0;     
    if (n->key > key)     
        return cauta_tr(n->l, key);     
    else if (n->key < key)     
        return cauta_tr(n->r, key);     
    return 1;     
}     
     
int main()     
{     
    srand(time(0));     
    freopen("zeap.in","r",stdin);     
    freopen("zeap.out","w",stdout);     
    rad_tr = nil = new treap(0, 0, ms, -ms, ms, NULL, NULL);     
    while (!feof(stdin))     
    {     
        scanf("%c", &oper);     
        if (oper != 'M')     
            scanf("%ld\n", &x);     
        else scanf("%c\n", &op2);     
        if (oper == 'I')     
        {     
            insert_tr(rad_tr, x, rand() % max_pon + 1);     
            ct++;     
        }     
        if (oper == 'S')     
            if (cauta_tr(rad_tr, x) == 1)     
            {     
                ct--;     
                erase_tr(rad_tr, x);     
            }     
            else printf("-1\n");     
        if (oper == 'C')     
            printf("%ld\n", cauta_tr(rad_tr, x));     
        if (oper == 'M' && ct < 2)     
            printf("-1\n");     
        else     
        {     
            if (oper == 'M' && op2 == 'A')     
                printf("%ld\n", rad_tr->max - rad_tr->min);     
            if (oper == 'M' && op2 == 'I')     
                printf("%ld\n", rad_tr->difm);     
        }     
    }     
    fclose(stdin);     
    fclose(stdout);     
    return 0;