#include <fstream>
#include <time.h>
#include <stdlib.h>
#define INF 1e9
using namespace std;
ifstream in ("zeap.in");
ofstream out("zeap.out");
string str;
bool ok;
struct node{
int key, priority, min, max, difmin;
node *left, *right;
node();
node (int key, int priority, node *left, node *right, int min, int max, int difmin){
this->key = key;
this->priority = priority;
this->left = left;
this->right = right;
this->min = min;
this->max = max;
this->difmin = difmin;
}
}*root, *nil;
void refresh(node *&nod){
nod->min = min(nod->key, min(nod->left->min, nod->right->min));
nod->max = max(nod->key, max(nod->left->max, nod->right->max));
nod->difmin = min(min(nod->left->difmin, nod->right->difmin), min(nod->key - nod->left->max, nod->right->min - nod->key));
}
void rotateLeft(node *&nod){
node *temp = nod->right;
nod->right = temp->left;
temp->left = nod;
nod = temp;
refresh(nod);
refresh(nod->left);
}
void rotateRight(node *&nod){
node *temp = nod->left;
nod->left = temp->right;
temp->right = nod;
nod = temp;
refresh(nod);
refresh(nod->right);
}
void balance(node *&nod){
if(nod->priority < nod->left->priority){
rotateRight(nod);
}
if(nod->priority < nod->right->priority){
rotateLeft(nod);
}
}
void insert(node *&nod, int key, int priority){
if(nod == nil){
nod = new node(key, priority, nil, nil, key, key, INF);
return;
}
if(nod->key < key){
insert(nod->right, key, priority);
}
else if(nod->key > key){
insert(nod->left, key, priority);
}
balance(nod);
refresh(nod);
}
void erase(node *&nod, int key){
if(nod == nil){
ok = 0;
return;
}
if(nod->key == key){
if(nod->left == nod->right && nod->left == nil){
delete nod;
nod = nil;
}
else{
if(nod->right->priority > nod->left->priority){
rotateLeft(nod);
erase(nod, key);
}
else{
rotateRight(nod);
erase(nod, key);
}
}
}
else{
if(nod->key < key){
erase(nod->right, key);
}
else{
erase(nod->left, key);
}
}
if(nod != nil)
refresh(nod);
}
bool search(node *&nod, int key){
if(nod == nil){
return false;
}
if(nod->key == key)
return true;
if(nod->key < key){
return search(nod->right, key);
}
else{
return search(nod->left, key);
}
}
int main(int argc, const char * argv[]) {
nil = new node(0, 0, NULL, NULL, INF, -INF, INF);
root = nil;
int key;
srand(time(0));
while(in>>str){
if(str == "I"){
in>>key;
insert(root, key, rand());
}else if(str == "S"){
ok = true;
in>>key;
erase(root, key);
if(ok == 0)
out<<"-1\n";
}else if(str == "C"){
in>>key;
out<<search(root, key)<<'\n';
}else if(str == "MAX"){
out<<root->max - root->min<<'\n';
}else if(str == "MIN"){
out<<root->difmin<<'\n';
}
}
return 0;
}