#include <bits/stdc++.h>

using namespace std;

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

struct treap
{
    int key , priority , vmax , vmin , difmin;
    treap *left ;
    treap *right ;
    treap() {}
    treap ( int key , int priority , treap *left , treap * right )
    {
        this->vmax=key;
        this->vmin=key;
        this->key=key;
        this->priority=priority ;
        this->left=left;
        this->right=right;
        this->difmin=0x3f3f3f3f;
    }
};

treap * nill , *root;

void calcv(treap * nod )
{
    nod->vmin = nod->key ;
    nod->vmax = nod->key ;
    nod->difmin = 0x3f3f3f3f;
    if ( nod->left != nill )
    {
        nod->vmin = min(nod->vmin,nod->left->vmin) ;
        nod->difmin = min(nod->difmin,nod->left->difmin) ;
        nod->difmin = min(nod->difmin,nod->key - nod->left->vmax) ;
    }
    if ( nod->right != nill )
    {
        nod->vmax = max(nod->vmax,nod->right->vmax) ;
        nod->difmin = min(nod->difmin,nod->right->difmin) ;
        nod->difmin = min(nod->difmin,nod->right->vmin - nod->key) ;
    }
}

void rotleft(treap * & nod )
{
    treap * aux = nod->left;
    nod->left = aux->right ;
    aux->right = nod;
    nod = aux;
    calcv(nod) ;
    calcv(aux) ;
}

void rotright(treap * &nod )
{
    treap * aux = nod->right ;
    nod->right = aux->left ;
    aux->left = nod;
    nod = aux;
    calcv(nod) ;
    calcv(aux) ;
}

void balance( treap * & nod )
{
    if ( nod->left->priority > nod->priority )
        rotleft(nod) ;
    if ( nod->right->priority > nod->priority )
        rotright(nod) ;
}

void adaug(treap * & nod , int key ,int priority )
{
    if ( nod == nill )
    {
        nod = new treap (key,priority,nill,nill) ;
        return;
    }
    if ( nod->key > key )
        adaug(nod->left,key,priority) ;
    else
        adaug(nod->right,key,priority) ;
    balance(nod) ;
    calcv(nod) ;
}

bool cauta(treap *nod , int key)
{
    if ( nod == nill )
        return false ;
    if ( nod->key == key )
        return true ;
    if ( nod->key > key )
        return cauta(nod->left,key) ;
    else
        return cauta(nod->right,key) ;
}

void sterg(treap * & nod , int key )
{
    if ( nod == nill )
    {
        fout << "-1" << '\n' ;
        return ;
    }
    if ( nod->key > key )
        sterg(nod->left,key) ;
    else if ( nod->key < key )
        sterg(nod->right,key) ;
    else
    {
        if ( nod->left == nill && nod->right == nill )
        {
            delete nod ;
            nod = nill;
            return ;
        }
        else
        {
            if ( nod->left->priority > nod->right->priority )
                rotleft(nod);
            else
                rotright(nod) ;
            sterg(nod,key);
        }
    }
    balance(nod) ;
    calcv(nod) ;
}

void inorder(treap *nod)
{
    if ( nod == nill )
        return ;
    inorder(nod->left);
    fout << nod->key << " " ;
    inorder(nod->right) ;
}

int main()
{
    string sir;
    int nr;
    srand(unsigned(time(0))) ;
    root = nill = new treap (0,0,NULL,NULL) ;
    while ( fin >> sir )
    {
        if ( sir[0] == 'I' )
        {
            fin >> nr;
            adaug(root,nr,rand()+1) ;
        }
        else if ( sir[0] == 'S' )
        {
            fin >> nr;
            sterg(root,nr) ;
        }
        else if (sir[0] == 'C' )
        {
            fin >> nr ;
            fout << cauta(root,nr) << '\n' ;
        }
        else if ( sir[1] == 'I' )
        {
            if ( root == nill || root->difmin == 0x3f3f3f3f )
            {
                fout << "-1" << '\n' ;
                continue ;
            }
            fout << root->difmin << '\n' ;
        }
        else
        {
            if ( root == nill )
            {
                fout << "-1" << '\n' ;
                continue ;
            }
            fout << root->vmax - root->vmin << '\n' ;
        }
    }
}