#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <limits>
#include <time.h>
#include <cstdlib>
using namespace std;

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

struct Node {
    long long priority;
    long long key;
    long long maxkey;
    long long minkey;
    long long mindif;
    Node *left, *right;
    Node(long long p, long long k,  Node* l = nullptr, Node* r = nullptr) : 
        priority(p), key(k), left(l), right(r)
    {
        minkey = key;
        maxkey = key;
        mindif = numeric_limits<long long>::max();

    }
    Node(const Node& ref) : 
        priority(ref.priority), key(ref.key), left(ref.left), right(ref.right)
    {

    }
    ~Node()
    {
        if (left) {
            delete left;
        }
        if (right) {
            delete right;
        }

    }
    void print()
    {
       // cout << "(" << key << ", " << priority << ", " << minkey << ", " << maxkey << ", " << mindif <<") ";
    }
};
class Zeap
{
    
public:
    Zeap():m_root(nullptr)
    {
        srand(time(NULL));
    }
    ~Zeap(){}
    long long max_dif()
    {
        if (m_root) {
            if (m_root->left || m_root->right) {
               return m_root->maxkey - m_root->minkey;
            }
        }
        return -1;

    }
    long long min_dif()
    {
        if (m_root) {
            if (m_root->left || m_root->right) {
                return m_root->mindif;
            }
        }
        return -1;
    }
    void insert(long long key)
    {
        if (!m_root) {
           // cout << "initialize root with key " << key << "\n";
            m_root = new Node(rand(), key);
        } else {
            m_root = _insert(key, m_root);
        }
    }
    void del(long long key)
    {
        
        m_root = _del(key, m_root);
    }
    long long search(long long key)
    {
        return _search(key, m_root);

    }
    void print()
    {
        if (!m_root) {
           // cout << "EMPTY TREE\n";
        } else {
            _print(m_root);
           // cout << "\n";
        }

    }
private:
    Node* _del(long long key, Node* node)
    {

        if (node == nullptr) {
            return node;
        }
       // cout << "del key " << key << " in " << node->key << " " << node->priority << "\n";
        if (key < node->key) {
            node->left = _del(key, node->left);
        } 
        else if (key > node->key) {
            node->right = _del(key, node->right);
        } 
        else if (!node->right) {
            Node* tmp = node->left;

            node->left = nullptr;
            node->right = nullptr;
            delete node;

            node = tmp;
        } else if (!node->left) {
            Node* tmp = node->right;

            node->left = nullptr;
            node->right = nullptr;
            delete node;

            node = tmp;
        } else if (node->left->priority < node->right->priority) {
            node = _rotate_left(node);
            node->left = _del(key, node->left);
        } else { 
            node = _rotate_right(node);
            node->right = _del(key, node->right);
        }
        _update(node);
        return node;
    }
    Node* _insert(long long key, Node* node)
    {
        //cout << "insert " << key << " in node (" << node->key << ", " << node->priority << ")\n";
        if (key < node->key) {
            //add left
            if (!node->left) {
                node->left = new Node(rand(), key);
            }
            else {
                node->left =  _insert(key, node->left);
            }
        }
        else {
            if (!node->right) {
                node->right = new Node(rand(), key);
            }
            else {
                node->right = _insert(key, node->right);
            }
        }
        return _balance(node);
    }
    Node* _balance(Node* node)
    {
        if (node->left) {
            if (node->priority < node->left->priority) {
                node = _rotate_right(node);
            }
        }
        if (node->right) {
            if (node->priority < node->right->priority) {
                node = _rotate_left(node);
            }
        }
        _update(node);
        return node;
    }
    void _update(Node* node)
    {
        if (!node) {
            return;
        }
        node->minkey = node->key;
        node->maxkey = node->key;
        node->mindif = numeric_limits<long long>::max();

        if (node->left) {
            node->minkey = min(node->minkey, node->left->minkey);
            node->maxkey = max(node->maxkey, node->left->maxkey);
            node->mindif = min(node->mindif, node->left->mindif);
            node->mindif = min(node->mindif, node->key - node->left->maxkey);
        }
        if (node->right) {
            node->minkey = min(node->minkey, node->right->minkey);
            node->maxkey = max(node->maxkey, node->right->maxkey);
            node->mindif = min(node->mindif, node->right->mindif);
            node->mindif = min(node->mindif, node->right->minkey - node->key);
        }
    }
    void _print(Node* node)
    {
        if (!node) {
            return;
        }
        
        _print(node->left);
        node->print();
        _print(node->right);

    }
    Node* _rotate_left(Node* node)
    {

        if (node->right) {
       // cout << "Left rotation in " << node->key << " " << node->priority << "\n";
            Node* T2 = node->right->left;
            Node* y = node->right;
            y->left = node;
            node->right = T2;
            _update(node);
            return y;
        }
        else {
            return node;
        }
    }
    Node* _rotate_right(Node* node)
    {

        if (node->left) {
       // cout << "Right rotation in " << node->key << " " << node->priority << "\n";
            Node* T2 = node->left->right;
            Node* x = node->left;

            x->right = node;
            node->left = T2;
            _update(node);
            return x;
        }
        else {
            return node;
        }
    }
    long long _search(long long key, Node* node)
    {
        if (!node) {
            return 0;
        }
        if (key == node->key) {
            return 1;
        }
        else {
            if (key < node->key) {
                return _search(key, node->left);
            } else {
                return _search(key, node->right);
            }

        }

    }
    bool leaf(Node* node)
    {
        return (!node->left && !node->right);
    }
    Node* m_root;
};

Zeap zeap;

int main()
{
    string line;
    while (getline(in, line)) {

        if (line.substr(0, 3).compare("MAX") == 0) {
            out << zeap.max_dif() << "\n";
            continue;
        }
        if (line.substr(0,3).compare("MIN") == 0) {
            out << zeap.min_dif() << "\n";
            continue;
        }
        char type = line[0];
        long long key = stoll(line.substr(2));


        if (type == 'I') {
            if (!zeap.search(key)) {
                zeap.insert(key);
                zeap.print();

            }
            else {
               // cout << "Key " << key << " already present\n";

            }
            continue;
        }
        if (type == 'S') {
           // cout << "Del key " << key << "\n";
            if (zeap.search(key))
                zeap.del(key);
            else { 

                out << "-1\n";
             //   cout << "Key " << key << " not found\n";
            }
            zeap.print();
            continue;
        }
        if (type == 'C') {
            out << zeap.search(key) << "\n";
            continue;
        }

    }


}