#include <iostream>
#include <fstream>
#include <ctime>
#include <random>
#include <string>
using namespace std;
const int INF = 1000000000;
class Treap
{
public:
struct nod
{
int mn, mx, difMin;
int val, priority;
nod *fiuSt, *fiuDr;
};
Treap(nod *root = nullptr)
{
nil = new nod;
nil->priority = nil->val = -1;
if(root == nullptr)
this->root = nil;
else
this->root = root;
srand(time(0));
}
void Insert(int val)
{
Insert(root, rand(), val);
}
void Split(int val, Treap &st, Treap &dr)
{
nod *retSt, *retDr;
Split(root, val, retSt, retDr);
st = Treap(retSt);
dr = Treap(retDr);
}
//that > this
void Join(Treap &that)
{
root = Join(root, that.root);
that = Treap();
}
void Erase(int val)
{
Erase(root, val);
}
bool Find(int val)
{
return Find(root, val);
}
int MaxDif()
{
return root->mx - root->mn;
}
int MinDif()
{
return root->difMin;
}
private:
void Update(nod * x)
{
if(x != nil)
{
x->mn = x->mx = x->val;
x->difMin = INF;
if(x->fiuSt != nil)
{
x->mn = min(x->mn, x->fiuSt->mn);
x->difMin = min(x->difMin, min(x->fiuSt->difMin, x->val - x->fiuSt->mx));
}
if(x->fiuDr != nil)
{
x->mx = max(x->mx, x->fiuDr->mx);
x->difMin = min(x->difMin, min(x->fiuDr->difMin, x->fiuDr->mn - x->val));
}
}
}
void Split(nod *current, int val, nod * &st, nod * &dr)
{
if(current == nil)
st = dr = nil;
else if(val < current->val)
{
dr = current;
Split(current->fiuSt, val, st, current->fiuSt);
}
else
{
st = current;
Split(current->fiuDr, val, current->fiuDr, dr);
}
Update(current);
}
nod * Join(nod * st, nod * dr)
{
if(st == nil)
return dr;
if(dr == nil)
return st;
if(st->priority >= dr->priority)
{
st->fiuDr = Join(st->fiuDr, dr);
Update(st);
return st;
}
dr->fiuSt = Join(st, dr->fiuSt);
Update(dr);
return dr;
}
void Insert(nod * ¤t, int priority, int val)
{
if(priority > current->priority)
{
nod * st, * dr;
Split(current, val, st, dr);
current = new nod;
current->val = val, current->priority = priority;
current->fiuSt = st, current->fiuDr = dr;
Update(current);
return;
}
if(val < current->val)
Insert(current->fiuSt, priority, val);
else
Insert(current->fiuDr, priority, val);
Update(current);
}
void Erase(nod * ¤t, int val)
{
if(val == current->val)
{
nod * t = current;
current = Join(current->fiuSt, current->fiuDr);
delete t;
Update(current);
return;
}
if(val < current->val)
Erase(current->fiuSt, val);
else
Erase(current->fiuDr, val);
Update(current);
}
bool Find(nod * current, int val)
{
if(current == nil)
return false;
if(val == current->val)
return true;
if(val < current->val)
return Find(current->fiuSt, val);
return Find(current->fiuDr, val);
}
nod * root, * nil;
};
int main()
{
ifstream in("zeap.in");
ofstream out("zeap.out");
string type;
int x;
Treap treap;
while(in >> type)
{
if(type == "I")
{
in >> x;
if(treap.Find(x) == false)
treap.Insert(x);
}
else if(type == "S")
{
in >> x;
if(treap.Find(x) == false)
out << -1 << "\n";
else
treap.Erase(x);
}
else if(type == "C")
{
in >> x;
out << treap.Find(x) << "\n";
}
else if(type == "MAX")
out << treap.MaxDif() << "\n";
else
out << treap.MinDif() << "\n";
}
in.close();
out.close();
return 0;
}