#include <cstdio>
#include <algorithm>

const int Pmask = 524287;
const int Inf = 0x3F3F3F3F;

using namespace std;

struct Treap {
    int key, priority;
    int minDif;
    int maxKey, minKey;
    Treap *left, *right;
    Treap (int k, int p, int mD, int mK, int mk, Treap *l, Treap *r) {
        key = k;
        priority = p;
        minDif = mD;
        maxKey = mK;
        minKey = mk;
        left = l;
        right = r;
    }
};

Treap *R, *NIL;

void updateNode(Treap* &N) {
    if (N == NIL) {
        return;
    }
    N->minDif = Inf;
    N->maxKey = N->key;
    N->minKey = N->key;
    if (N->left != NIL) {
        N->minDif = min(min(N->key - N->left->maxKey, N->left->minDif),
                        N->minDif);
        N->minKey = min(N->minKey, N->left->minKey);
    }
    if (N->right != NIL) {
        N->minDif = min(min(N->right->minKey - N->key, N->right->minDif),
                        N->minDif);
        N->maxKey = max(N->maxKey, N->right->maxKey);
    }
}

void leftBalance(Treap* &N) {
    Treap *T = N->left;
    N->left = T->right;
    T->right = N;
    updateNode(N);
    N = T;
    updateNode(N);
}

void rightBalance(Treap* &N) {
    Treap *T = N->right;
    N->right = T->left;
    T->left = N;
    updateNode(N);
    N = T;
    updateNode(N);
}

void balance(Treap* &N) {
    if (N->left->priority > N->priority) {
        leftBalance(N);
    } else if (N->right->priority > N->priority) {
        rightBalance(N);
    }
    updateNode(N);
}

void treapInsert(Treap* &N, int key, int priority) {
    if (N == NIL) {
        N = new Treap(key, priority, Inf, key, key, NIL, NIL);
        return;
    }
    if (key < N->key) {
        treapInsert(N->left, key, priority);
    } else if (key > N->key) {
        treapInsert(N->right, key, priority);
    }
    balance(N);
}

void treapErase(Treap* &N, int key) {
    if (N == NIL) {
        return;
    }
    if (key < N->key) {
        treapErase(N->left, key);
    } else if (key > N->key) {
        treapErase(N->right, key);
    } else {
        if (N->left == NIL && N->right == NIL) {
            delete N;
            N = NIL;
        } else {
            if (N->left->priority > N->right->priority) {
                leftBalance(N);
            } else {
                rightBalance(N);
            }
            treapErase(N, key);
        }
    }
    updateNode(N);
}

bool treapFind(Treap *N, int key) {
    if (N == NIL) {
        return 0;
    }
    if (key == N->key) {
        return 1;
    }
    if (key < N->key) {
        return treapFind(N->left, key);
    } else {
        return treapFind(N->right, key);
    }
}

void inOrder(Treap *N) {
    if (N == NIL) {
        return;
    }
    inOrder(N->left);
    printf("%d %d %d %d\n", N->key, N->minKey, N->maxKey, N->minDif);
    inOrder(N->right);
}

inline unsigned xor128(void) {
    static unsigned X = 123456789U, Y = 362436069U, Z = 521288629U, W = 88675123U;
    unsigned T = X ^ (X << 11U);
    X = Y;
    Y = Z;
    Z = W;
    return W = W ^ (W >> 19U) ^ (T ^ (T >> 8U));
}

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

    R = NIL = new Treap(0, 0, 0, 0, 0, NULL, NULL);

    while (scanf(" %c", &opType) != EOF) {
        if (opType == 'I') {
            scanf("%d", &x);
            treapInsert(R, x, (xor128() & Pmask) + 1);
        } else if (opType == 'S') {
            scanf("%d", &x);
            if (treapFind(R, x)) {
                treapErase(R, x);
            } else {
                puts("-1");
            }
        } else if (opType == 'C') {
            scanf("%d", &x);
            putchar('0' + treapFind(R, x));
            putchar('\n');
        } else {
            if (getchar() == 'A') {
                if (R == NIL || (R->left == NIL && R->right == NIL)) {
                    puts("-1");
                } else {
                    printf("%d\n", R->maxKey - R->minKey);
                }
            } else {
                if (R == NIL || (R->left == NIL && R->right == NIL)) {
                    puts("-1");
                } else {
                    printf("%d\n", R->minDif);
                }
            }
            getchar();
        }
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}