#include <bits/stdc++.h>

using namespace std;

#define FILE_IO

class Treap
{
private:
    struct _treap
    {
        int key, priority;
        int mxdif, mndif, mx, mn;
        _treap *lft, *rgt, *fth;

        _treap()
        {
            key = priority = 0;
            mxdif = mndif = -1;
            mx = 0;
            mn = 1 << 30;
            lft = rgt = 0;
        }

        _treap(int _key, int _priority)
        {
            key = _key;
            priority = _priority;
            lft = rgt = 0;
            mxdif = mndif = -1;
            mx = mn = key;
        }
    }*R, *nil;

    int getRandomPriority()
    {
        int mod = (1 << 30) - 1;
        int priority = (rand() & mod) + 1;
        return priority;
    }

    void Balance(_treap *&T)
    {
        if(T -> priority < T -> lft -> priority)
            leftRotate(T);
        if(T -> priority < T -> rgt -> priority)
            rightRotate(T);

        fix(T -> lft);
        fix(T -> rgt);
        fix(T);
    }

    void leftRotate(_treap *&T)
    {
        _treap *_T;
        _T = T -> lft;
        T -> lft = _T -> rgt;
        _T -> rgt = T;
        T = _T;
    }

    void rightRotate(_treap *&T)
    {
        _treap *_T;
        _T = T -> rgt;
        T -> rgt = _T -> lft;
        _T -> lft = T;
        T = _T;
    }

    void fix(_treap *&T)
    {
        if(T == nil)
            return;

        T -> mn = min(T -> lft -> mn, T -> rgt -> mn);
        T -> mn = min(T -> key, T -> mn);
        T -> mx = max(T -> lft -> mx, T -> rgt -> mx);
        T -> mx = max(T -> key, T -> mx);

        if(T -> mn == T -> mx)
            T -> mndif = T-> mxdif = -1;
        else
        {
            T -> mxdif = T -> mx - T -> mn;
            T -> mndif = T -> mxdif;
            if(T -> lft != nil)
            {
                if(T -> lft -> mndif != -1)
                    T -> mndif = min(T -> mndif, T -> lft -> mndif);
                T -> mndif = min(T -> mndif, T -> key - T -> lft -> mx);
            }
            if(T -> rgt != nil)
            {
                if(T -> rgt -> mndif != -1)
                    T -> mndif = min(T -> mndif, T -> rgt -> mndif);
                T -> mndif = min(T -> mndif, T -> rgt -> mn - T -> key);
            }
        }
    }

    bool Insert(_treap *&T, int key, int priority)
    {
        if(T == nil)
        {
            T = new _treap(key, priority);
            T -> lft = T -> rgt = nil;
            return 1;
        }

        if(T -> key > key)
            Insert(T -> lft, key, priority);
        else if(T -> key < key)
            Insert(T -> rgt, key, priority);
        else
            return 0;

        Balance(T);
    }

    bool Erase(_treap *&T, int val)
    {
        if(T == nil)    return 0;

        bool ret = 0;
        if(T -> key > val)
            ret = Erase(T -> lft, val);
        else if(T -> key < val)
            ret = Erase(T -> rgt, val);
        else
        {
            if(T -> lft == nil && T -> rgt == nil)
            {
                delete T;
                T = nil;
                return 1;
            }
            else
            {
                if(T -> lft -> priority > T -> rgt -> priority)
                    leftRotate(T);
                else
                    rightRotate(T);
                ret = Erase(T, val);
            }
        }

        fix(T -> lft);
        fix(T -> rgt);
        fix(T);
        return ret;
    }

    bool Search(_treap *&T, int val)
    {
        if(T == nil)    return 0;
        if(T -> key == val) return 1;
        if(T -> key > val)  return Search(T -> lft, val);
        if(T -> key < val)  return Search(T -> rgt, val);
        return 0;
    }

public:
    void init()
    {
        R = nil = new _treap;
    }

    void Insert(int x)
    {
        Insert(R, x, getRandomPriority());
    }

    bool Erase(int x)
    {
        return Erase(R, x);
    }

    bool Search(int x)
    {
        return Search(R, x);
    }

    int MAX() {return R -> mxdif;}
    int MIN() {return R -> mndif;}
}T;

int main()
{
    #ifdef FILE_IO
    freopen("zeap.in", "r", stdin);
    freopen("zeap.out", "w", stdout);
    #endif

    srand(time(0));
    T.init();

    char op;
    while(1)
    {
        op = getchar();
        int x;
        if(op == 'I')   /// Insert
        {
            scanf("%d", &x);
            T.Insert(x);
        }
        else if(op == 'S')  /// Erase
        {
            scanf("%d", &x);
            if( !T.Erase(x) )
                printf("-1\n");
        }
        else if(op == 'C')  /// Search
        {
            scanf("%d", &x);
            printf("%d\n", T.Search(x));
        }
        else if(op == 'M')
        {
            op = getchar();
            if(op == 'A')   /// Max
                printf("%d\n", T.MAX());
            else if(op == 'I')  /// Min
                printf("%d\n", T.MIN());
        }
        else
            break;

        while(op != '\n')
            op = getchar();
    }

    return 0;
}