#include <fstream>
#include <algorithm>
using namespace std;
typedef struct Treap * Arbore;
typedef pair <Arbore, Arbore> Paa;
Arbore NIL;
struct Treap
{
int min, max, g, difmin, val, prio;
Arbore st, dr;
Treap(int _val) : val(_val), prio(rand()), min(_val), max(_val), difmin(1e9), g(1), st(NIL), dr(NIL) { }
~Treap() {
if (st != NIL)
delete st;
if (dr != NIL)
delete dr;
}
};
Arbore join(Arbore a, Arbore b);
Paa split(Arbore x, int val);
void process(Arbore x);
bool check(Arbore x, int val);
Arbore sterge(Arbore x, int val);
Arbore insert(Arbore x, int val);
char input[100];
ifstream in("zeap.in");
ofstream out("zeap.out");
int main()
{
NIL = new Treap(0);
NIL->st = NIL->dr = NIL;
NIL->g = 0;
Arbore k = NIL;
int x;
while (in >> input) {
switch(input[0]) {
case 'I':
in >> x;
k = insert(k, x);
break;
case 'S':
in >> x;
k = sterge(k, x);
break;
case 'C':
in >> x;
out << check(k, x) << '\n';
break;
default:
if (k->min == k->max)
out << "-1\n";
else if (input[1] == 'A')
out << k->max - k->min << '\n';
else
out << k->difmin << '\n';
break;
}
}
}
Arbore insert(Arbore x, int val)
{
if (check(x, val))
return x;
Paa ans = split(x, val);
Arbore nod = new Treap(val);
return join(join(ans.first, nod), ans.second);
}
Arbore sterge(Arbore x, int val)
{
Paa s1 = split(x, val);
Paa s2 = split(s1.first, val - 1);
if (s2.second == NIL)
out << "-1\n";
return join(s2.first, s1.second);
}
bool check(Arbore x, int val)
{
if (x->val == val)
return 1;
if (x == NIL)
return 0;
if (x->val > val)
return check(x->st, val);
return check(x->dr, val);
}
Paa split(Arbore x, int val)
{
if (x == NIL)
return { NIL, NIL };
if (x->val <= val) {
Paa ans = split(x->dr, val);
x->dr = NIL;
process(x);
return { join(x, ans.first), ans.second };
}
Paa ans = split(x->st, val);
x->st = NIL;
process(x);
return { ans.first, join(ans.second, x) };
}
Arbore join(Arbore a, Arbore b)
{
if (a == NIL)
return b;
if (b == NIL)
return a;
if (a->val > b->val)
swap(a, b);
if (a->prio > b->prio) {
a->dr = join(a->dr, b);
process(a);
return a;
}
b->st = join(a, b->dr);
process(b);
return b;
}
void process(Arbore x)
{
x->g = 1 + x->st->g + x->dr->g;
x->min = x->max = x->val;
x->difmin = 1e9;
if (x->st != NIL) {
x->min = x->st->min;
x->difmin = min(x->difmin, x->val - x->st->max);
x->difmin = min(x->difmin, x->st->difmin);
}
if (x->dr != NIL) {
x->max = x->dr->max;
x->difmin = min(x->difmin, x->dr->min - x->val);
x->difmin = min(x->difmin, x->dr->difmin);
}
}