#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <fstream>
using namespace std;
fstream f("zeap.in");
ofstream g("zeap.out");
struct Node
{
    int val;
    Node* left;
    Node* right;
    Node(int v) : val(v), left(NULL), right(NULL) {}
};

void insert(Node*& root, int val)
{
    if (!root)
    {
        root = new Node(val);
    }
    else if (val < root->val)
    {
        insert(root->left, val);
    }
    else if (val > root->val)
    {
        insert(root->right, val);
    }
}

int search(Node* root, int val)
{
    if (!root)
    {
        return 0;
    }
    else if (val == root->val)
    {
        return 1;
    }
    else if (val < root->val)
    {
        return search(root->left, val);
    }
    else
    {
        return search(root->right, val);
    }
}

int remove(Node*& root, int val)
{
    if (!root)
    {
        return -1;
    }
    else if (val == root->val)
    {
        int ret = root->val;
        if (!root->left && !root->right)
        {
            delete root;
            root = NULL;
        }
        else if (!root->left || !root->right)
        {
            Node* tmp = root;
            root = root->left ? root->left : root->right;
            delete tmp;
        }
        else
        {
            Node* minNode = root->right;
            while (minNode->left)
            {
                minNode = minNode->left;
            }
            root->val = minNode->val;
            remove(root->right, minNode->val);
        }
        return ret;
    }
    else if (val < root->val)
    {
        return remove(root->left, val);
    }
    else
    {
        return remove(root->right, val);
    }
}

void inorder(Node* root, int& prev, int& minDiff, int& maxDiff)
{
    if (root)
    {
        inorder(root->left, prev, minDiff, maxDiff);
        if (prev != -1)
        {
            int diff = abs(root->val - prev);
            if (diff < minDiff || minDiff == -1)
            {
                minDiff = diff;
            }
            if (diff > maxDiff)
            {
                maxDiff = diff;
            }
        }
        prev = root->val;
        inorder(root->right, prev, minDiff, maxDiff);
    }
}

int main()
{
    Node* root = NULL;
    char op;
    int x, prev = -1, minDiff = -1, maxDiff = -1;
    while (scanf("%c %d", &op, &x) == 2)
    {
        switch (op)
        {
        case 'I':
            insert(root, x);
            break;
        case 'S':
            cout << remove(root, x) << endl;
            break;
        case 'C':
            inorder(root, prev, minDiff, maxDiff);
            if (minDiff == -1 || maxDiff == -1)
            {
                cout << "0\n";
            }
            else
            {
                cout << maxDiff - minDiff << endl;
            }
            prev = -1;
            minDiff = -1;
            maxDiff = -1;
            break;
        default:
            break;
        }
    }

    return 0;
}