#include <fstream>
using namespace std;

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

#define NEDEFINIT 2147483647

struct Nod {
  int valoare;
  Nod *stanga;
  Nod *dreapta;
  int h;
  int x;
  int minim;
  int maxim;

  Nod(int val) : valoare(val), stanga(NULL), dreapta(NULL), h(1), x(NEDEFINIT), minim(valoare), maxim(valoare){};
};

int calculMinGap(Nod *nod){
    int a,b,c,d;
    a=b=c=d=NEDEFINIT;
    if(nod->stanga != NULL) {
        a = nod->stanga->x;
        c = nod->valoare - nod->stanga->maxim;
    }

    if(nod->dreapta != NULL) {
        b = nod->dreapta->x;
        d = nod->dreapta->minim - nod->valoare;
    }

    int minGap = min(a,min(b,min(c,d)));

    return minGap;
}

int calculMaxim(Nod* nod){
    //if(nod==NULL)
    //    return 0;
    if(nod->stanga == NULL){
        if(nod->dreapta == NULL)
            return nod->valoare;
        return max(nod->valoare, nod->dreapta->maxim);
    }
    else{
        if(nod->dreapta == NULL)
            return max(nod->valoare, nod->stanga->maxim);

        return max(max(nod->valoare, nod->stanga->maxim), nod->dreapta->maxim);
    }
}

int calculMinim(Nod* nod){
    //if(nod==NULL)
    //    return NEDEFINIT;
    if(nod->stanga == NULL){
        if(nod->dreapta == NULL)
            return nod->valoare;
        return min(nod->valoare, nod->dreapta->minim);
    }
    else{
        if(nod->dreapta == NULL)
            return min(nod->valoare, nod->stanga->minim);

        return min(min(nod->valoare, nod->stanga->minim), nod->dreapta->minim);
    }
}

int calculHeight(Nod* nod){
    if(nod == NULL)
        return 0;
    if(nod->stanga==NULL){
        if(nod->dreapta==NULL)
            return 0;

        return nod->dreapta->h+1;
    }
    else{
        if(nod->dreapta==NULL)
            return nod->stanga->h+1;

        if(nod->stanga->h > nod->dreapta->h)
            return nod->stanga->h+1;
        else
            return nod->dreapta->h+1;
    }
}

Nod *rotireDreapta(Nod *deRotit1) {
  Nod *deRotit2 = deRotit1->stanga;
  Nod *deMutat = deRotit2->dreapta;
  deRotit2->dreapta = deRotit1;
  deRotit1->stanga = deMutat;
  deRotit1->h = calculHeight(deRotit1);
  deRotit1->maxim = calculMaxim(deRotit1);
  deRotit1->minim = calculMinim(deRotit1);
  deRotit1->x = calculMinGap(deRotit1);
  deRotit2->h = calculHeight(deRotit2);
  deRotit2->maxim = calculMaxim(deRotit2);
  deRotit2->minim = calculMinim(deRotit2);
  deRotit2->x = calculMinGap(deRotit2);
  return deRotit2;
}

Nod *rotireStanga(Nod *deRotit1) {
  Nod *deRotit2 = deRotit1->dreapta;
  Nod *deMutat = deRotit2->stanga;
  deRotit2->stanga = deRotit1;
  deRotit1->dreapta = deMutat;
  deRotit1->h = calculHeight(deRotit1);
  deRotit1->maxim = calculMaxim(deRotit1);
  deRotit1->minim = calculMinim(deRotit1);
  deRotit1->x = calculMinGap(deRotit1);
  deRotit2->h = calculHeight(deRotit2);
  deRotit2->maxim = calculMaxim(deRotit2);
  deRotit2->minim = calculMinim(deRotit2);
  deRotit2->x = calculMinGap(deRotit2);
  return deRotit2;
}

int getBalanta(Nod *nod) {
  if (nod == NULL)
    return 0;
  return calculHeight(nod->stanga) -
       calculHeight(nod->dreapta);
}

Nod *insereaza(Nod *curent, int valoare) {
  if (curent == NULL)
    return new Nod(valoare);
  if (valoare < curent->valoare)
    curent->stanga = insereaza(curent->stanga, valoare);
  else if (valoare > curent->valoare)
    curent->dreapta = insereaza(curent->dreapta, valoare);
  else
    return curent;


  curent->h = calculHeight(curent);
  curent->h = calculHeight(curent);
  curent->maxim = calculMaxim(curent);
  curent->minim = calculMinim(curent);
  curent->x = calculMinGap(curent);

  int balanta = getBalanta(curent);
  if (balanta > 1) {
    if (valoare < curent->stanga->valoare) {
      return rotireDreapta(curent);
    } else if (valoare > curent->stanga->valoare) {
      curent->stanga = rotireStanga(curent->stanga);
      return rotireDreapta(curent);
    }
  }
  if (balanta < -1) {
    if (valoare > curent->dreapta->valoare) {
      return rotireStanga(curent);
    } else if (valoare < curent->dreapta->valoare) {
      curent->dreapta = rotireDreapta(curent->dreapta);
      return rotireStanga(curent);
    }
  }
  return curent;
}


Nod *getMinim(Nod *curent) {
  while (curent->stanga != NULL)
    curent = curent->stanga;
  return curent;
}

Nod* getMaxim(Nod *curent){
    while(curent->dreapta != NULL)
        curent = curent->dreapta;
    return curent;
}

Nod *sterge(Nod *curent, int valoare) {
  if (curent == NULL){
    fout<<"-1\n";
    return curent;
  }
  if (valoare < curent->valoare)
    curent->stanga = sterge(curent->stanga, valoare);
  else if (valoare > curent->valoare)
    curent->dreapta = sterge(curent->dreapta, valoare);
  else {
    if ((curent->stanga == NULL) ||
      (curent->dreapta == NULL)) {
      Nod *temp = curent->stanga ? curent->stanga : curent->dreapta;
      if (temp == NULL) {
        temp = curent;
        curent = NULL;
      } else
        *curent = *temp;
      free(temp);
    } else {
      Nod *temp = getMinim(curent->dreapta);
      curent->valoare = temp->valoare;
      curent->dreapta = sterge(curent->dreapta,
                   temp->valoare);
    }
  }

  if (curent == NULL)
    return curent;


  curent->h = calculHeight(curent);
  curent->maxim = calculMaxim(curent);
  curent->minim = calculMinim(curent);
  curent->x = calculMinGap(curent);
  int balanta = getBalanta(curent);
  if (balanta > 1) {
    if (getBalanta(curent->stanga) >= 0) {
      return rotireDreapta(curent);
    } else {
      curent->stanga = rotireStanga(curent->stanga);
      return rotireDreapta(curent);
    }
  }
  if (balanta < -1) {
    if (getBalanta(curent->dreapta) <= 0) {
      return rotireStanga(curent);
    } else {
      curent->dreapta = rotireDreapta(curent->dreapta);
      return rotireStanga(curent);
    }
  }
  return curent;
}


int cautaElement(Nod* root, int valoare){
    if(root==NULL){
        return 0;
    }

    if(root->valoare==valoare)
        return 1;
    else if(root->stanga!=NULL && valoare < root->valoare)
        return cautaElement(root->stanga, valoare);
    else if(root->dreapta!=NULL && valoare > root->valoare)
        return cautaElement(root->dreapta, valoare);

    return 0;
}

int main() {
  Nod *root = NULL;

  string optiune;
  int x;
  while(fin>>optiune){
    if(optiune[0]=='I'){
        fin>>x;
        root=insereaza(root, x);
    }
    else if(optiune[0]=='S'){
        fin>>x;
        root=sterge(root, x);
    }
    else if(optiune[0]=='C'){
        fin>>x;
        fout<<cautaElement(root, x)<<"\n";
    }
    else if(optiune[1]=='A'){
        if(root==NULL || (root->stanga == NULL && root->dreapta == NULL))
            fout<<"-1\n";
        else
            fout<<root->maxim - root->minim<<"\n";
    }
    else{
        if(root==NULL || (root->stanga == NULL && root->dreapta == NULL))
            fout<<"-1\n";
        else
            fout<<root->x<<"\n";
    }
  }
}