#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;
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);
		if (oper == 'S')
			if (cauta_tr(rad_tr, x) == 1)
				erase_tr(rad_tr, x);
			else printf("-1\n");
		if (oper == 'C')
			printf("%ld\n", cauta_tr(rad_tr, x));
		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;
}