#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define mp make_pair
#define CHECK(x) if(!(x)) return false;
#define CHECKRET(x, y) if(!(x)) return (y);
#define SKIP(x) if((x)) continue;
typedef pair<int, int> pii;
#ifdef INFOARENA
#define ProblemName "zeap"
#endif
#define MCONCAT(A, B) A B
#ifdef ProblemName
#define InFile MCONCAT(ProblemName, ".in")
#define OuFile MCONCAT(ProblemName, ".out")
#else
#define InFile "fis.in"
#define OuFile "fis.out"
#endif
struct node {
int key, y, secondaryKey;
node* left;
node* right;
int size;
int minelem, maxelem, mindelta;
node(int k, int sk) {
key = k;
secondaryKey = sk;
left = right = 0;
size = 1;
y = rand();
minelem = maxelem = k;
mindelta = INT_MAX;
}
};
inline bool isSmaller(int key, int sk, node *n) {
if (key < n->key) return true;
if (key > n->key) return false;
return (sk < n->secondaryKey);
}
inline int size(node *p) {
return p ? p->size : 0;
}
inline int minelem(node *p) {
return p ? p->minelem : INT_MAX;
}
inline int maxelem(node *p) {
return p ? p->maxelem : INT_MIN;
}
inline int mindelta(node *p) {
return p ? p->mindelta : INT_MAX;
}
void recalc(node* p) {
if (!p) return;
p->size = size(p->left) + size(p->right) + 1;
p->minelem = min(p->key, min(minelem(p->left), minelem(p->right)));
p->maxelem = max(p->key, max(maxelem(p->left), maxelem(p->right)));
p->mindelta = INT_MAX;
if (p->left) {
p->mindelta = min(p->mindelta, p->left->mindelta);
p->mindelta = min(p->mindelta, p->key - p->left->maxelem);
}
if (p->right) {
p->mindelta = min(p->mindelta, p->right->mindelta);
p->mindelta = min(p->mindelta, p->right->minelem - p->key);
}
}
void tsplit(node *root, int k, node **l, node **r, int sk) {
if (root == NULL) {
*l = NULL;
*r = NULL;
return;
}
if (isSmaller(k, sk, root)) {
tsplit(root->left, k, l, &root->left, sk);
*r = root;
recalc(root);
}
else {
tsplit(root->right, k, &root->right, r, sk);
*l = root;
recalc(root);
}
}
node *tmerge(node *l, node *r) {
if (l == NULL) return r;
if (r == NULL) return l;
if (l->y < r->y) {
r->left = tmerge(l, r->left);
recalc(r);
return r;
}
else {
l->right = tmerge(l->right, r);
recalc(l);
return l;
}
}
node *tadd(node *root, node *n) {
if (root == NULL) return n;
if (n->y > root->y) {
node *r, *l;
tsplit(root, n->key, &l, &r, n->secondaryKey);
n->left = l;
n->right = r;
recalc(n);
return n;
}
if (isSmaller(n->key, n->secondaryKey, root))
root->left = tadd(root->left, n);
else
root->right = tadd(root->right, n);
recalc(root);
return root;
}
node *tremove(node *root, int k) {
if (root == NULL)
return root;
if (root->key == k) {
node *bak = root;
root = tmerge(root->left, root->right);
delete bak;
return root;
}
if (isSmaller(k, 0, root))
root->left = tremove(root->left, k);
else root->right = tremove(root->right, k);
recalc(root);
return root;
}
node *tkthelement(node *root, int k) {
if (root == NULL)
return NULL;
if (size(root->left) == k - 1)
return root;
if (size(root->left) >= k)
return tkthelement(root->left, k);
return tkthelement(root->right, k - size(root->left) - 1);
}
inline void tIntervalSplit(node *root, int x, int y, node **l, node **mid, node **r) {
node *splitNode = tkthelement(root, x);
tsplit(root, splitNode->key, l, mid, splitNode->secondaryKey - 1);
splitNode = tkthelement(*mid, y - size(*l));
tsplit(*mid, splitNode->key, mid, r, splitNode->secondaryKey);
}
inline node *tIntervalMerge(node *l, node *mid, node *r) {
node *root = tmerge(l, mid);
return tmerge(root, r);
}
#define MPRINTPOS 100
#define MPRINTLVL 10
char printBuf[MPRINTLVL][MPRINTPOS];
char auxbuf[20];
void _tprint(node *root, int lvl = 0, int pleft = 0, int pright = MPRINTPOS) {
if (root == NULL) return;
int mid = (pleft + pright) / 2;
sprintf(auxbuf, "%d (%d)", root->key, root->mindelta);
memcpy(&printBuf[lvl][mid], auxbuf, strlen(auxbuf));
_tprint(root->left, lvl + 1, pleft, mid);
_tprint(root->right, lvl + 1, mid, pright);
}
void tprint(node *root) {
for (int i = 0; i < MPRINTLVL; ++i)
for (int j = 0; j < MPRINTPOS; ++j)
printBuf[i][j] = ' ';
_tprint(root, 0, 0, size(root) * 5);
for (int i = 0; i < MPRINTLVL; ++i) {
for (int j = 0; j < MPRINTPOS; ++j)
putchar(printBuf[i][j]);
putchar('\n');
}
}
int texists(node **root, int k) {
node *l, *r;
tsplit(*root, k, &l, &r, INT_MAX);
int rez = (size(l) > 0 && maxelem(l) == k) ? 1 : 0;
*root = tmerge(l, r);
return rez;
}
int main() {
assert(freopen(InFile, "r", stdin));
assert(freopen(OuFile, "w", stdout));
srand(41532);
node *T = NULL;
//int Q;
//scanf("%d", &Q);
int nseed = 0;
for (;;) {
char c;
int x = 0, y = 0;
node *l, *mid, *r;
if (scanf(" %c", &c) != 1) break;
int itmp; char tmp;
switch (c) {
case 'I':
scanf("%d", &x);
if (texists(&T, x) == 1)
break;
T = tadd(T, new node(x, nseed++));
break;
case 'S':
scanf("%d", &x);
itmp = size(T);
T = tremove(T, x);
if (size(T) == itmp) puts("-1");
break;
case 'C':
scanf("%d", &x);
printf("%d\n", texists(&T, x));
break;
case 'M':
//scanf("%d%d", &x, &y);
tmp = getchar(); getchar();
x = 0, y = size(T) - 1;
if (x >= y) {
puts("-1");
break;
}
++x, ++y;
tIntervalSplit(T, x, y, &l, &mid, &r);
if (tmp == 'I')
printf("%d\n", mid->mindelta);
else printf("%d\n", mid->maxelem - mid->minelem);
T = tIntervalMerge(l, mid, r);
break;
default:
break;
}
//printf("---- %c %d %d ----\n", c, x, y);
//puts("---- Trie is ----\n");
//tprint(T);
}
return 0;
}