#include <iostream>
#include <fstream>
#include <vector>
#include <string.h>
using namespace std;
ofstream out ("zeap.out");
ifstream in ("zeap.in");
int a=-1,b,c,t1,t2;
struct node
{
    int key;
    node *left, *right;
};
//vector<int> v;
node* node1;
char op[13];
int key,stop;
void Afisare1(node*r)
{
    if(r != NULL)
    {
        Afisare1(r->left);
        cout<<r->key<<" ";
        Afisare1(r->right);
    }
}
void Afisare(node *r)
{

    if(r != NULL)
    {
        Afisare(r->left);
        if(b!=1000000001 && a>(r->key-b))
           {
               t1=r->key;
               t2=b;

            a=r->key-b;
    }
b=r->key;
        Afisare(r->right);
    }
    //cout<<endl;

}
int Afisare6(node *r)
{
    if(!r)
        return -1;
    node* aux1;
    node* aux2;
    if(r->left==NULL && r->right==NULL)
        return -1;


//     for (int i=1; i<v.size(); ++i)
//        out<<v[i]-v[i-1]<<" ";
//        out<<endl;
     a=1000000001;
     c=b=1000000001;
 Afisare(r);




    return a;


}


node* zigRotation(node* x)
{
    node* y = x->left;
    x->left = y->right;
    y->right = x;
    return y;

}
node* zagRotation(node* x)
{
    node* y = x->right;
    x->right = y->left;
    y->left = x;
    return y;
}


node* splay(node* root, int key)
{
    if (root == NULL || root->key == key)
        return root;

    if (root->key > key) /// se duce in stanga
    {
        if (root->left == NULL) ///  e liber copilul , facem doar o rotatie ca sa ajunga noul copil parinte
            return root;
        if (root->left->key>key) /// mergem inca un copil mai jos si apelam recursiv de la nepot , facand o zig-zig rotation
        {
            root->left->left = splay(root->left->left, key);
            if(root->left->left!= NULL)
                root->left= zigRotation(root->left);
        }
        else if (root->left->key < key) /// mergem inca un copil mai jos si apelam recursiv de la nepot , facand o zig-zag rotation
        {
            root->left->right= splay(root->left->right, key);
            if (root->left->right != NULL)
                root->left = zagRotation(root->left);
        }
        if(root->left==NULL)
            return root;
        return zigRotation(root);

    }
    else /// se duce in dreapta
    {
        if (root->right == NULL) /// e liber copilul , facem doar o rotatie ca sa ajunga noul copil parinte
            return root;
        if (root->right->key > key) /// mergem inca un copil mai jos si apelam recursiv de la nepot , facand o zag-zig rotation
        {
            root->right->left=splay(root->right->left, key);
            if (root->right->left != NULL)
                root->right = zigRotation(root->right);
        }
        else if (root->right->key<key) /// mergem inca un copil mai jos si apelam recursiv de la nepot , facand o zag-zag rotation
        {
            root->right->right= splay(root->right->right, key);
            if(root->right->right!= NULL)
                root->right = zagRotation(root->right);
        }
        if(root->right == NULL)
            return root;
        return zagRotation(root);

    }
}


bool search1(node *root, int key)
{
    if(root==NULL)
        return false;
    if (root->key == key)
        return true;
    if(root->key>key)
        return search1(root->left,key);
    return search1(root->right,key);
}

 node* deletion( node* root, int key)
{
     node* aux;
    if (root==NULL)
    {
        out<<-1<<endl;
        return NULL;
    }


    if(search1(root,key))/// daca valoarea e in tree
        root = splay(root, key);
    else
    {
        out<<-1<<endl;
        return root;
    }



    if (root->left==NULL)/// daca nu am copil stang
    {
        return root->right;
    }


    else /// daca am fiu stang, il duc in varf si inlocuiesc noul fiu drept cu fostul fiu drept, asa practic elimin vechiul varf
    {
        aux = root->right;
        root = splay(root->left, key);
        root->right = aux;
    }

    return root;
}

node* insert(node* root, int key)
{
    node* aux = new node;
    aux->key = key;
    aux->left = aux->right = NULL;

    if (root == NULL)
        return aux;

    root = splay(root, key);

    if (root->key == key)
        return root;

    if (root->key > key)
    {
        aux->right = root;
        aux->left = root->left;
        root->left = NULL;
    }
    else
    {
        aux->left = root;
        aux->right = root->right;
        root->right = NULL;
    }
    return aux;
}

int MAXI(node* root)
{
    if(!root)
        return -1;
    node* aux1;
    node* aux2;
    if(root->left==NULL && root->right==NULL)
        return -1;



    if(root->left==NULL)
    {
        aux1=root->right;

        while(aux1->right!=NULL)
            aux1=aux1->right;
        return abs(aux1->key-root->key);
    }

    if(root->right==NULL)
    {
        aux2=root->left;
        while(aux2->left!=NULL)
            aux2=aux2->left;
        return abs(root->key-aux2->key);
    }

    aux1=root->right;
    while(aux1->right!=NULL)
        aux1=aux1->right;


    aux2=root->left;
    while(aux2->left!=NULL)
        aux2=aux2->left;


    return abs(aux1->key - aux2->key);

}

int MINI(node* root,int key)
{
    node* aux;
    if(search1(root,key))
        return key;
    root=insert(root,key);
    if(root->right==NULL)
    {
        node1=deletion(root,key);
        return 0;
    }
    aux=root->right;

    while(aux->left)
        aux=aux->left;
    node1=deletion(root,key);
    return aux->key;
}


int main()
{
    node* root = NULL;
//    root = insert(root, 100);
//    root = insert(root, 50);
//    root = insert(root, 200);
//    root = insert(root, 40);
//    root = insert(root, 60);
//    root = insert(root, 312);
//    root = insert(root, 10);
//    root = insert(root, 502);
//    root = insert(root, 21200);
//    root = insert(root, 403);
//    root = insert(root, 6);
//    root = insert(root, 32);


//    cout << "Inorder traversal of the modified Splay tree: \n";
//    Afisare(root);
//    cout<<endl; root=deletion(root,100);
//    root=deletion(root,50);
//    root=deletion(root,10);
//    root=deletion(root,10);
    node1=root;
//    cout<<endl<<MAXI(node1,55)<<endl;
//    cout<<MAXI(node1,4)<<endl;
//    cout<<MAXI(node1,3)<<endl;
//    cout<<MAXI(node1,78)<<endl;
//    cout<<MAXI(node1,15)<<endl;
//    cout<<MAXI(node1,50)<<endl;
//    cout<<MAXI(node1,784)<<endl;
//    cout<<MINI(node1,10)<<endl;
//    cout<<MINI(node1,101)<<endl;
//    cout<<MINI(node1,2440)<<endl;

    int q;
   // cin>>q;



        while(in.getline(op,12))
        {


        //cout<<op;
        if(op[0]=='I') // INSERT
        {
            char p[12];
            strcpy(p,op+2);
           // cout<<strlen(p)<<endl;
            int sum=0;
            for( int i = 0 ; i<strlen(p);i++)
            {
                sum*=10;
                sum+=p[i]-'0';

            }
            if(sum<=t1 && sum>=t2)
            {
                if(sum>=t2)
                {


                    a=sum-t2;
                    sum=t1;
                }
                else
                {

                        t2=sum;
                        a=t1-sum;

                }
            }



            node1 = insert(node1, sum);

//            Afisare1(node1);
//            cout<<endl;
        }
        if(op[0]=='S') // STERGE
        {
            char p[12];
            strcpy(p,op+2);
           // cout<<strlen(p)<<endl;
            int sum=0;
            for( int i = 0 ; i<strlen(p);i++)
            {
                sum*=10;
                sum+=p[i]-'0';

            }
            a=-1;

            node1=deletion(node1,sum);

        }
        if(op[1]=='A') // MAX
        {

            out<<MAXI(node1)<<endl;
        }
        if(op[1]=='I') //MIN
        { bool ok=0;
            if(!node1)
       {
           out<<-1;
           ok=1;
       }
    if(node1->left==NULL && node1->right==NULL && ok==0)
    {
        out<<-1;
        ok=1;
    }

            if(a==-1 && ok==0)
            //cout<<Afisare(node1)<<endl;
            out<<Afisare6(node1)<<endl;
            else if(ok==0)
            out<<a;
        }
        if(op[0]=='C') // CAUTARE
        {
             char p[12];
            strcpy(p,op+2);
           // cout<<strlen(p)<<endl;
            int sum=0;
            for( int i = 0 ; i<strlen(p);i++)
            {
                sum*=10;
                sum+=p[i]-'0';

            }

            out<<search1(node1,sum)<<endl;
        }


     }
    //Afisare(node1);
    return 0;
}