#include <stdio.h>
#include <stdlib.h>
#define inf 2000000005
using namespace std;
FILE  *pf1= fopen("zeap.in", "r");
FILE  *pf2=fopen("zeap.out", "w");
char sir[50];
long int nrel;
int ok;
struct treap
{
    treap *left, *right;
    long int cheie, prior, maxi, mini, difmin;
    ///maxi= maximul cheilor din subarborele cu radacina in  nod, inclusiv el
    ///mini= minimul cheilor din subarborele cu radacina in  nod, inclusiv el
    ///difmin- dif minima a cheilor din subarborele cu radacina in nod, inclusiv el,sau inf
}*rad;
long int minim(long int a, long int b)
{
    return (a<b? a: b);
}
long int maxim(long int a, long int b)
{
    return (a>b? a: b);
}
void update(treap *&nod)
{
    nod->maxi=nod->mini=nod->cheie;
    nod->difmin=inf;
    if(nod->left!=0)
    {
        ///nod->cheie mai mare decat toate cheile din stanga
        nod->mini=nod->left->mini;
        nod->difmin=minim(nod->left->difmin, nod->cheie- nod->left->maxi);
    }
    if(nod->right!=0)
    {
        nod->maxi=nod->right->maxi;
        ///nod->cheie mai imc decat toate cheile din dreapta
        nod->difmin=minim(nod->difmin, minim(nod->right->difmin,  nod->right->mini- nod->cheie));
    }
}
void creare_nod(treap *&nod, long int prior, long int cheie)
{
    nod=new treap;
    nod->left=nod->right=0;
    nod->cheie=cheie;
    nod->prior=prior;
    nod->maxi=nod->mini=nod->cheie;
    nod->difmin=inf;
    update(nod);
    if(nrel==0) rad=nod;
}
void rotatie_st(treap *&nod)
{
    treap *aux;
    aux=nod->left;
    nod->left=aux->right;
    aux->right=nod;
    nod=aux;
    update(nod->right);
}
void rotatie_dr(treap *&nod)
{
    treap * aux;
    aux=nod->right;
    nod->right=aux->left;
    aux->left=nod;
    nod=aux;
    update(nod->left);
}
void insereaza(treap *&nod, long int prior, long int cheie)
{
    if(nod== NULL) creare_nod(nod, prior, cheie);
    else if(nod->cheie> cheie)
    {
        insereaza(nod->left, prior, cheie);
        if((nod->left!=NULL)&&(nod->left->prior> nod->prior)) rotatie_st(nod);
        update(nod);///in fct de fii
    }
    else if(nod->cheie==cheie) ok=0;
         else
         {
             insereaza(nod->right, prior, cheie);
             if((nod->right!=NULL)&&(nod->right->prior> nod->prior)) rotatie_dr(nod);
             update(nod);///in fct de fii
         }
}
void sterge(treap *&nod, long int cheie)
{
    ///daca x nu e in zeap afisezi -1
    if(nod==NULL) {ok=0; fprintf(pf2, "%s\n", "-1");}///nodul de sters nu exista
    else if(nod->cheie> cheie) {sterge(nod->left, cheie);}///cauti nodul de sters
    else if(nod->cheie< cheie) {sterge(nod->right, cheie);}
    else
    {
       ///ai gasit nodul de sters
        if((nod->left==NULL)&&(nod->right==NULL)) {delete nod; nod=NULL;}
        else if(nod->right== NULL) {treap *aux=nod->left; delete nod; nod=aux;}
             else if(nod->left== NULL) {treap *aux=nod->right; delete nod; nod=aux;}
                  else
                  {
                      ///rotesti nodul cu fiul cu prioritate maxima si te duci recursiv in jos pana ajungi pe frunza/ 1 fiu
                      if(nod->left->prior> nod->right->prior) {rotatie_st(nod);sterge(nod->right, cheie);}
                      else {rotatie_dr(nod);sterge(nod->left, cheie);}
                  }
    }
    if(nod!=NULL)  update(nod);
}
int cauta(treap *nod, long int cheie)
{
  if(nod==NULL) return 0;
  else if(nod->cheie> cheie) return cauta(nod->left, cheie);
       else if(nod->cheie< cheie) return cauta(nod->right, cheie);
            else  return 1;
}
long int maxim(treap *&rad)
{
   if(nrel<2) return -1;
   else return (rad->maxi- rad->mini);
}
long int minim(treap *&rad)
{
    if(nrel<2) return -1;
    else  return rad->difmin;
}
int main()
{
    long int var, rez;
    while(fgets(sir, 50, pf1))
    {
        if(sir[0]=='I') {var=atol(sir+2); ok=1; insereaza(rad, labs(rand())%inf+1, var); if(ok)nrel++;}
        else if(sir[0]=='S') {var=atol(sir+2); ok=1; sterge(rad, var); if(ok) nrel--;}
             else if(sir[0]=='C') {var=atol(sir+2); rez=cauta(rad, var); fprintf(pf2, "%ld\n", rez);}
                  else if(sir[1]=='A') {rez= maxim(rad); fprintf(pf2, "%ld\n", rez);}
                       else if(sir[1]=='I') {rez= minim(rad); fprintf(pf2, "%ld\n", rez);}


    }
    return 0;
}