#include <bits/stdc++.h>
using namespace std;
ifstream f("zeap.in");
ofstream g("zeap.out");
const int inf=1e9;
bool ok;
struct T{
int key,priority,_min,_max,_mindst;
T *left,*right;
T() {}
T(int key,int priority,T* left,T* right){
this->key=key;
this->priority=priority;
this->left=left,this->right=right;
this->_min=key;
this->_max=key;
this->_mindst=1e9;
}
} *R,*nil;
void upd(T* &n){
if(n==nil)return ;
int Lmin,Lmax,Lmindst,Rmin,Rmax,Rmindst;
if(n->left!=nil){
Lmin=n->left->_min;
Lmax=n->left->_max;
Lmindst=n->left->_mindst;
}else{
Lmin= 1e9;
Lmax=-1e9;
Lmindst=1e9;
}
if(n->right!=nil){
Rmin=n->right->_min;
Rmax=n->right->_max;
Rmindst=n->right->_mindst;
}else{
Rmin= 1e9;
Rmax=-1e9;
Rmindst=1e9;
}
n->_min=min(n->key,min(Lmin,Rmin));
n->_max=max(n->key,max(Lmax,Rmax));
n->_mindst=min(min(n->key-Lmax,Rmin-n->key),min(Lmindst,Rmindst));
return ;
}
int search(T* n,int key){
if(n==nil)return 0;
if(n->key==key)return 1;
if(key<n->key)
return search(n->left,key);
return search(n->right,key);
}
void rotleft(T* &n){
T *t=n->left;
n->left=t->right,t->right=n;
upd(n),upd(t);
n=t;
}
void rotright(T* &n){
T* t=n->right;
n->right=t->left,t->left=n;
upd(n),upd(t);
n=t;
}
void balance(T* &n){
if(n->left->priority>n->priority)
rotleft(n);
else if(n->right->priority>n->priority)
rotright(n);
upd(n->left);upd(n->right);upd(n);
}
void insert(T* &n,int key,int priority){
if(n==nil){
n=new T(key,priority,nil,nil);
return ;
}
if(key<n->key)
insert(n->left,key,priority);
else if(key>n->key)
insert(n->right,key,priority);
balance(n);
}
void erase(T* &n,int key){
if(n==nil)return ;
if(n->key<key)
erase(n->right,key);
else if(n->key>key)
erase(n->left,key);
else{
ok=1;
if(n->left==nil&&n->right==nil){
delete n,n=nil;
}else{
(n->left->priority>n->right->priority)?rotleft(n):rotright(n);
erase(n,key);
}
}
upd(n);
}
//pair<T*,T*> split(T* &n,int key){
// insert(n,key,inf);
// return {n->left,n->right};
//}
//void join(T* &R,T* lft,T *rgt,int key){
// T* R=new T(key,0,lft,rgt);
// erase(R,R->key);
//}
int main()
{
srand(time(0));
R=nil=new T(0,0,nil,nil);
string c;int val,cnt=0;
while(f>>c){
if(c[0]=='I'){
f>>val;cnt++;
insert(R,val,rand()+1);
}
if(c[0]=='S'){
ok=0;f>>val;
erase(R,val);
if(!ok)
g<<-1<<'\n';
else
cnt--;
}
if(c[0]=='C'){
f>>val;
g<<search(R,val)<<'\n';
}
if(c[1]=='A'){
if(cnt>=2)
g<<(R->_max-R->_min)<<'\n';
else
g<<-1<<'\n';
}
if(c[1]=='I'){
if(cnt>=2)
g<<(R->_mindst)<<'\n';
else
g<<-1<<'\n';
}
}
return 0;
}