#include <fstream>
#include <time.h>
#include <stdlib.h>
#define INF 1e9

using namespace std;

ifstream in ("zeap.in");
ofstream out("zeap.out");

string str;

int nrNodes;

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;
            -- nrNodes;
        }
        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"){
            ++ nrNodes;
            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"){
            if(nrNodes > 1)
                out<<root->max - root->min<<'\n';
            else{
                out<<"-1\n";
            }
            
        }else if(str == "MIN"){
            if(nrNodes > 1)
                out<<root->difmin<<'\n';
            else{
                out<<"-1\n";
            }
        }
    }
    return 0;
}