#include <iostream>
#include <fstream>
#include <vector>
#include <cmath>

using namespace std;

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

const int INF = 2e9;

class Treap {
public:
  
  Treap () {
    root = nill = new Node (INF, 0, nullptr, nullptr);
  }

  void Insert (int val) {
    m_Insert (val, root);
  }

  void Erase (int val) {
    m_Erase (val, root);
  }

  bool Find (int val) {
    return m_Find (val, root);
  }

  int GetMaxDiff () {
    return root -> maxVal - root -> minVal;
  }

  int GetMinDiff () {
    return root -> best;
  }

private:

  struct Node {

    Node (int v, int p, Node *l, Node *r) {
      this -> val = v;
      this -> priority = p;
      this -> left = l;
      this -> right = r;
      this -> best = INF;
      this -> minVal = v;
      this -> maxVal = v;
    }

    int val, best, priority, maxVal, minVal;
    Node *left, *right;
  };

  Node *nill, *root;
 
  void m_RoatateLeft (Node *&curNode) {
  
    Node *aux = curNode -> right;
    curNode -> right = curNode -> right -> left;
    aux -> left = curNode;
    curNode = aux;
  }

  void m_RoatateRight (Node *&curNode) {
  
    Node *aux = curNode -> left;
    curNode -> left = curNode -> left -> right;
    aux -> right = curNode;
    curNode = aux;
  }

  void m_Balance (Node *&curNode) {

    if (curNode -> left -> priority > curNode -> priority) {
      m_RoatateRight (curNode);
    }
    else if (curNode -> right -> priority > curNode -> priority) {
      m_RoatateLeft (curNode);
    }
  }

  void m_Update (Node *&curNode) {

    curNode -> best = INF;
    curNode -> minVal  = curNode -> maxVal  = curNode -> val;

    if (curNode -> left != nill) {
      curNode -> minVal = min (curNode -> minVal, curNode -> left -> minVal);
      curNode -> best = min (curNode -> best, curNode -> left -> best);
      curNode -> best = min (curNode -> best, curNode -> val - curNode -> left -> maxVal);
    }

    if (curNode -> right != nill) {
      curNode -> maxVal = max (curNode -> maxVal, curNode -> right -> maxVal);
      curNode -> best = min (curNode -> best, curNode -> right -> best);
      curNode -> best = min (curNode -> best, curNode -> right -> minVal - curNode -> val);
    }
  }

  void m_Insert (int val, Node *&curNode) {

    if (curNode -> val == val) {
      return;
    }

    if (curNode == nill) {
      curNode = new Node (val, floor (rand ()) + 1, nill, nill);
      /* cerr << curNode -> val << ' ' << curNode -> best << '\n'; */
      return;
    }

    if (val > curNode -> val) {
      m_Insert (val, curNode -> right);
    }
    else {
      m_Insert (val, curNode -> left);
    }
  
    m_Balance (curNode);
    m_Update (curNode);
  }

  void m_Erase (int val, Node *&curNode) {
  
    if (curNode == nill) {
      fout << -1 << '\n';
      return;
    }

    if (val < curNode -> val) {
      m_Erase (val, curNode -> left);
    }
    else if (val > curNode -> val) {
      m_Erase (val, curNode -> right);
    }
    else {

      if (curNode -> left == nill and curNode -> right == nill) {
        delete curNode;
        curNode = nill;
        return;
      }

      if (curNode -> left -> priority < curNode -> right -> priority) {
        m_RoatateLeft (curNode);
        m_Erase (val, curNode);
      }
      else {
        m_RoatateRight (curNode);
        m_Erase (val, curNode);
      }
    }

    m_Update (curNode);
  }

  bool m_Find (int val, Node *curNode) {
  
    if (curNode == nill) {
      return false;
    }

    if (val < curNode -> val) {
      return m_Find (val, curNode -> left);
    }
    else if (val > curNode -> val) {
      return m_Find (val, curNode -> right);
    }
    return true;
  }
};

int main () {
  
  Treap *t = new Treap ();
  
  string s;
  while (fin >> s) {
  
    if (s == "I") {
      int val;
      fin >> val;
      t -> Insert (val);
    }
    else if (s == "S") {
      int val;
      fin >> val;
      t -> Erase (val);
    }
    else if (s == "C") {
      int val;
      fin >> val;
      fout << t -> Find (val) << '\n';
    }
    else if (s == "MAX") {
      fout << t -> GetMaxDiff () << '\n';
    }
    else {
      fout << t -> GetMinDiff () << '\n';
    }
  }
}