#include <bits/stdc++.h>
using namespace std;
ifstream fi("zeap.in");
ofstream fo("zeap.out");

struct Treap {
   int val, priority, subarb;
   Treap *left, *right;

   Treap(int val, int priority, int subarb, Treap *left, Treap *right) {
      this->val = val;
      this->priority = priority;
      this->left = left;
      this->right = right;
      this->subarb = subarb;
   }
} *T, *nil;

char A[50];
multiset <int> S;

int getRandom() {
   return 1LL * rand() % 10000 * 10000 + rand() % 10000;
}

void updSubarbore(Treap *&nod) {
   if (nod == nil)
      return;
   nod->subarb = 1 + nod->left->subarb + nod->right->subarb;
}

void rotToRight(Treap *&nod) {
   Treap *t = nod->left;
   nod->left = t->right; t->right = nod;
   nod = t;

   updSubarbore(nod->left);
   updSubarbore(nod->right);
   updSubarbore(nod);
}

void rotToLeft(Treap *&nod) {
   Treap *t = nod->right;
   nod->right = t->left; t->left = nod;
   nod = t;

   updSubarbore(nod->left);
   updSubarbore(nod->right);
   updSubarbore(nod);
}

void balans(Treap *&nod) {
   /*if (nod == nil)
      return;*/
   if (nod->left->priority > nod->priority)
      rotToRight(nod);
   else if (nod->right->priority > nod->priority)
      rotToLeft(nod);
}

void baga(Treap *&nod, int val) {
   if (nod == nil) {
      nod = new Treap(val, getRandom(), 1, nil, nil);
      return;
   }

   if (val < nod->val) {
      baga(nod->left, val);
      updSubarbore(nod);
   }
   else if (val > nod->val) {
      baga(nod->right, val);
      updSubarbore(nod);
   }

   balans(nod);
}

void scoate(Treap *&nod, int val) {
    if (nod == nil)
        return;

    if (val < nod->val) {
        scoate(nod->left, val);
        updSubarbore(nod);
    }
    else if (val > nod->val) {
        scoate(nod->right, val);
        updSubarbore(nod);
    }
    else {
        // sunt aici si vreau sa cobor. il aduc pe fiul cu prioritate mai mare
        if (nod->left == nil && nod->right == nil) {
            delete nod;
            nod = nil;
        }
        else {
            if (nod->left->priority > nod->right->priority)
                rotToRight(nod);
            else
                rotToLeft(nod);
            scoate(nod, val);
        }
    }
}

bool cauta(Treap *nod, int val) {
   if (nod == nil)
      return 0;

   if (nod->val == val)
      return 1;
   else if (val < nod->val)
      return cauta(nod->left, val);
   else
      return cauta(nod->right, val);
}

int getMax(Treap *nod) {
   if (nod == nil)
      return -1;

   return max(nod->val, getMax(nod->right));
}

int getMin(Treap *nod) {
   if (nod == nil)
      return 1000000001;

   return min(nod->val, getMin(nod->left));
}

int kthElement(Treap *nod, int k) {
   if (nod == nil)
      return -1;

   if (k > nod->subarb)
      return -1;

   if (k <= nod->left->subarb)
      return kthElement(nod->left, k);
   else if (k == nod->left->subarb + 1)
      return nod->val;
   else
      return kthElement(nod->right, k - (nod->left->subarb + 1));
}

int alCatulea(Treap *nod, int x) {
   if (nod == nil)
      return -1000000;

   if (x < nod->val)
      return alCatulea(nod->left, x);
   else if (x == nod->val)
      return nod->left->subarb + 1;
   else
      return nod->left->subarb + 1 + alCatulea(nod->right, x);
}

int main()
{
   srand(time(NULL));
   T = nil = new Treap(0, 0, 0, NULL, NULL);

   while (fi.getline(A + 1, 100)) {
      if (A[1] != 'M') {
         int x = 0;
         for (int i = 3; i <= strlen(A + 1); i++)
            x = x * 10 + (A[i] - '0');

         if (A[1] == 'I') {
            baga(T, x);

            int k = alCatulea(T, x);

            // elimin (k-1),(k+1)
            // adaug k,k-1   si    k,k+1
            int prev = -1, nxt = -1;
            if (k - 1 >= 1 && k - 1 <= T->subarb)
               prev = kthElement(T, k - 1);
            if (k + 1 >= 1 && k + 1 <= T->subarb)
               nxt = kthElement(T, k + 1);
            if (prev != -1 && nxt != -1)
               S.erase(nxt - prev);
            if (prev != -1)
               S.insert(x - prev);
            if (nxt != -1)
               S.insert(nxt - x);
         }
         else if (A[1] == 'S') {
            if (cauta(T, x) == 0)
               fo << -1 << "\n";
            else {
               int k = alCatulea(T, x);
               scoate(T, x);

               // elimin x, (k-1)    si    x, (k)
               // adaug k-1,k
               int aici = -1, prev = -1;
               if (k - 1 >= 1 && k - 1 <= T->subarb)
                  prev = kthElement(T, k - 1);
               if (k >= 1 && k <= T->subarb)
                  aici = kthElement(T, k);

               if (prev != -1)
                  S.erase(x - prev);
               if (aici != -1)
                  S.erase(aici - x);
               if (prev != -1 && aici != -1)
                  S.insert(aici - prev);
            }
         }
         else {
            fo << cauta(T, x) << "\n";
         }
      }
      else {
         if (T->subarb < 2) {
            fo << -1 << "\n";
         }
         else if (A[2] == 'A') {
            //diferenta maxima
            fo << getMax(T) - getMin(T) << "\n";
         }
         else {
            // diferenta minima
            fo << (*S.begin()) << "\n";
            /*fo << (S.size()) << "\n";
            for (auto x: S)
                fo << "." << x;
            fo << "\n";*/
         }
      }
   }

   return 0;
}