#include <iostream>
#include <fstream>
#include <cstdlib>
#include <ctime>
using namespace std;
ifstream fin("zeap.in");
ofstream fout("zeap.out");
#define cout fout
struct T{
    int key, priority, ma, mi, s, mindif, maxdif;
    T *left, *right;

    void sum()
    {
        s = 1;
        if(left->priority)
            s += left->s;
        if(right->priority)
            s += right->s;
    }
    void maxim()
    {
        ma = key;
        if(right->priority)
            ma = right->ma;
    }
    void minim()
    {
        mi = key;
        if(left->priority)
            mi = left->mi;
    }
    void mind()
    {
        mindif = (1<<30);
        if(left->priority)
            mindif = min(mindif, min(key - left->ma, left->mindif));
        if(right->priority)
            mindif = min(mindif, min(right->mi - key, right->mindif));
    }
    void maxd()
    {
        maxdif = ma - mi;
    }
    void f()
    {
        sum();
        maxim();
        minim();
        mind();
        maxd();
    }

    T(int k, int p, T* l, T* r)
    {
        key = k;
        priority = p;
        left = l;
        right = r;
    }
} *R, *nil;

void init()
{
    srand(time(0));
    R = nil = new T(0, 0, 0, 0);
}

void rotL(T *&n)
{
    T* x = n->left;
    n->left = x->right;
    x->right = n;
    n->f();
    n = x;
    n->f();
}

void rotR(T *&n)
{
    T* x = n->right;
    n->right = x->left;
    x->left = n;
    n->f();
    n = x;
    n->f();
}

void balance(T *&n)
{
    if(n->left->priority > n->priority)
        rotL(n);
    else if(n->right->priority > n->priority)
        rotR(n);
}

void insert(T*& n, int key, int priority)
{
    if(n == nil)
    {
        n = new T(key, priority, nil, nil);
        n->f();
        return;
    }
    if(n->key > key)
        insert(n->left, key, priority);
    else if(n->key < key)
        insert(n->right, key, priority);
    n->f();
    balance(n);
}

void erase(T*& n, int key)
{
    if(n == nil)
        return;
    if(n->key > key)
    {
        erase(n->left, key);
        n->f();
    }
    else if(n->key < key)
    {
        erase(n->right, key);
        n->f();
    }
    else
    {
        if(n->left == nil && n->right == nil)
        {
            delete n;
            n = nil;
            return;
        }
        if(n->left->priority > n->right->priority)
        {
            rotL(n);
            erase(n->right, key);
        }
        else{
            rotR(n);
            erase(n->left, key);
        }
        n->f();
    }
}

int search(T *&n, int key)
{
    if(n == nil)
        return 0;
    if(n->key == key)
        return 1;
    if(n->key > key)
        return search(n->left, key);
    return search(n->right, key);
}

void af(T *&n)
{
    if(n ==nil)
        return;
    af(n->left);
    cout << n->key << " ";
    af(n->right);
}

int main()
{
    char c[4];
    int n;
    init();
    while(fin)
    {
        c[0] = c[1] = 0;
        fin>>c;
        if(c[0]=='I')
        {
            fin>>n;
            insert(R, n, rand()+1);
        }
        if(c[0]=='S')
        {
            fin>>n;
            if(!search(R, n))
                cout << "-1\n";
            else
                erase(R, n);
        }
        if(c[0]=='C')
        {
            fin>>n;
            cout << search(R, n) << "\n";
        }
        if(c[1]=='A')
        {
            if(R == nil || (R->left == nil && R->right == nil))
                cout << "-1\n";
            else
                cout << R->maxdif << "\n";
        }
        if(c[1]=='I')
        {
            if(R == nil || (R->left == nil && R->right == nil))
                cout << "-1\n";
            else
                cout << R->mindif << "\n";
        }
    }
}