#include <fstream>
#include <iostream>
#include <stdlib.h>
#include <time.h>
#define INF 1000000001

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

int removed, x, numberNodes = 0;

struct treap {
    int value;
    int priority;
    int minimum;
    int maximum;
    int difMin;

    treap *left, *right;

    treap(int value, int priority, treap *left, treap *right, int minimum, int maximum, int difMin) {
        this->value = value;
        this->priority = priority;
        this->left = left;
        this->right = right;
        this->minimum = minimum;
        this->maximum = maximum;
        this->difMin = difMin;
    }
};

treap *r, *nil;

void show(treap *r, int level) {
    if (r != nil) {
        show(r->right, level+1);
        for (int i=1;i<=level;i++)
            cout<<"  ";
        cout<<r->value<<" "<<r->priority<<" "<<r->minimum<<" "<<r->maximum<<" "<<r->difMin<<"\n";
        show(r->left, level+1);
    }
}

void refresh(treap *r) {
    r->minimum = min(r->value, min(r->left->minimum, r->right->minimum));
    r->maximum = max(r->value, max(r->left->maximum, r->right->maximum));
    r->difMin = min(r->value - r->left->maximum, min( r->right->minimum - r->value, min(r->left->difMin, r->right->difMin)  )  );
}

void rotateRight(treap * &r) {
    treap *f = r->left;
    r->left = f->right;
    f->right = r;
    r = f;
    refresh(r->right);
    refresh(r);
}

void rotateLeft(treap * &r) {
    treap *f = r->right;
    r->right = f->left;
    f->left = r;
    r = f;
    refresh(r->left);
    refresh(r);
}

void balance(treap * &r) {
    if (r->left != NULL && r->priority < r->left->priority) {
        rotateRight(r);
    } else
        if (r->right != NULL && r->priority < r->right->priority)
            rotateLeft(r);
}

void insertNode(treap * &r, int value, int priority) {
    if (r == nil) {
        r = new treap(value, priority, nil, nil, value, value, INF);
        numberNodes ++;
        return;
    } else
        if (value < r->value)
            insertNode(r->left, value, priority);
        else
            if (value > r->value)
                insertNode(r->right, value, priority);
    balance(r);
    refresh(r);
}

void removeNode(treap * &r, int value) {
    if (r != nil) {
        if (r->value > value)
            removeNode(r->left, value);
        else
            if (r->value < value)
                removeNode(r->right, value);
            else {
                // r->value == value
                if (r->left == nil && r->right == nil) {
                    delete r;
                    numberNodes --;
                    r = nil;
                    removed = 1;
                } else {
                    if (r->left->priority > r->right->priority)
                        rotateRight(r);
                    else
                        rotateLeft(r);
                    removeNode(r, value);
                }
            }
        if (r != nil)
            refresh(r);
    }
}

int searchValue (treap *r, int x) {
    if (r == nil)
        return 0;
    else
        if (r->value == x)
            return 1;
        else
            if (x < r->value)
                return searchValue(r->left, x);
            else
                return searchValue(r->right, x);
}

char buff[20];

int main () {
    srand(time(0));

    r = nil = new treap(0, 0, NULL, NULL, INF, -INF, INF);
    while (fin>>buff) {
        if (buff[0] == 'I') {
            fin>>x;
            insertNode(r, x, rand());
            continue;
        }
        if (buff[0] == 'S') {
            fin>>x;
            removed = 0;
            removeNode(r, x);
            if (!removed)
                fout<<"-1\n";

            continue;
        }
        if (buff[0] == 'C') {
            fin>>x;
            fout<<searchValue(r, x)<<"\n";
            continue;
        }
        if (buff[1] == 'I') {
            fout<<(numberNodes >= 2 ? (r->difMin) : -1)<<"\n";
        } else {
//            cout<<r->maximum - r->minimum<<"\n";
//            show(r, 0);
//            cout<<"\n\n";

            fout<<(numberNodes >= 2 ? (r->maximum - r->minimum) : -1)<<"\n";
        }
    }

    return 0;
}