#include <fstream>
#include <iostream>
#include <stdlib.h>
#include <time.h>
#define INF 2147483647
using namespace std;
char buff[6000010];
int poz=0;
int getnr(){
int nr=0;
while ('0'>buff[poz] || buff[poz]>'9')
poz++;
while ('0'<=buff[poz] && buff[poz]<='9'){
nr=nr*10+buff[poz]-'0';
poz++;
}
return nr;
}
struct treap{
int key;
int pri;
int mindif;
int maxi;
int mini;
int subarb;
treap *st,*dr;
treap (int key,int pri,treap *st,treap *dr,int mindif,int maxi,int mini){
this->key=key;
this->pri=pri;
this->st=st;
this->dr=dr;
this->mindif=mindif;
this->maxi=maxi;
this->mini=mini;
}
};
treap *r,*nil;
void update (treap *&n){ /// update valorilor din n
n->maxi = max(n->key,max(n->st->maxi,n->dr->maxi));
n->mini = min(n->key,min(n->st->mini,n->dr->mini));
int sol=INF;
if (n->dr->mini != INF)
sol=min(sol,n->dr->mini - n->key);
if (n->st->maxi != -INF)
sol=min(sol,n->key - n->st->maxi);
n->mindif = min(sol,min(n->st->mindif,n->dr->mindif));
}
int cauta (treap *n,int key){
if (n==nil)
return 0;
else if (n->key==key)
return 1;
else if (n->key<key)
return cauta (n->dr,key);
else return cauta (n->st,key);
}
void left (treap *&n){
treap *y = n->st;
n->st = y->dr;
y->dr=n;
n=y;
update (n->dr);
update (n);
}
void right (treap *&n){
treap *y = n->dr;
n->dr = y->st;
y->st=n;
n=y;
update (n->st);
update (n);
}
void balance (treap*&n){
if (n->pri < n->st->pri) /// rotire stanga
left (n);
else if (n->pri < n->dr->pri) /// rotire dreapta
right(n);
}
void inser (treap *&n,int key,int pri){
//if (key==3)
// printf ("a");
if (n==nil){ /// e mom sa il adaug?
n = new treap (key,pri,nil,nil,INF,key,key);
return;
}
else {
if (key < n->key)
inser (n->st, key,pri);
else
inser (n->dr,key,pri);
}
balance (n);
if (n!=nil)
update (n); /// update valorile lui n ???
}
void eras (treap *&n,int key){
if (n==nil)
return;
if (key < n->key)
eras (n->st, key);
else if (key > n->key)
eras (n->dr,key);
else { /// l am gasit, il mut in jos pana e frunza
if (n->st == nil && n->dr == nil){ /// e frunza
delete n;
n=nil;
}
else { /// erase ca la heap
if (n->st->pri > n->dr->pri)
left(n);
else right(n);
eras (n,key);
}
}
if (n!=nil)
update (n); /// update valorile lui n ???
}
int main()
{
ifstream fin ("zeap.in");
ofstream fout ("zeap.out");
int x,tot=0;
srand (time(0));
r=nil=new treap(0,0,NULL,NULL,INF,-INF,INF);
while (fin>>buff){
poz=0;
if (buff[poz]=='I'){
poz++;
fin>>x;
//printf ("a");
if (!cauta(r,x)){ /// daca x nu exista deja in treap
inser (r,x,rand()+1);
tot++;
}
/// insert x in treap
}
else if (buff[poz]=='S'){
poz++;
fin>>x;
//printf ("n");
if (!cauta(r,x)){ /// daca nu exista
fout<<"-1\n";
}
else{
eras (r,x); /// sterge x din treap
tot--;
}
}
else if (buff[poz]=='C'){
poz++;
fin>>x;
fout<<cauta(r,x)<<"\n";
}
else {
if (tot <2)
fout<<"-1\n";
else{
if (buff[poz+1]=='A')
fout<<r->maxi - r->mini<<"\n";
else fout<<r->mindif<<"\n";
}
poz+=3;
}
}
return 0;
}