//如果要删除和修改堆中任意一个元素的话，要存 堆中每个元素的在堆数组中的下标和插入数下标k（从1开始）的映射关系
//ph[k] = i 是插入数下标k映射到堆数组下标i。也就是第k个插入的结点的堆数组下标是i。 i, k从1开始的。记住ph放插入数下标返回堆数组下标
//hp[i] = k 是堆数组下标i映射到插入数下标k。也就是堆数组中下标为i的结点是第k个插入的结点。记住hp放堆数组下标返回插入数下标
//因为要删除和修改任意元素，这就要修改swap（）函数 成heap_swap(),这样在变动down，up的过程中（值变化的过程中）堆数组的下标和插入数的下标保持不变
#include <iostream>
#include <cstring>

using namespace std;

const int N = 100010; // 1e5次操作，也最多是插入1e5个结点，结点数最多这么多

// h[i]存储第i个结点的下标
//ph[i]存储插入数下标i的堆数组下标
//hp[i]存储堆数组下标i的插入数下标
//siz 表示堆数组大小，而且时刻指向堆数组最后已用的下标
//idx 表示插入数下标，而且时刻指向插入数最后已用的下标
int h[N], ph[N], hp[N], siz, idx; 

//交换两结点的数值，插入数下标是跟着数值改变而改变的，而它对应的堆数组下标是跟着插入数下标改变而改变的。
//每个结点都通过它的下标u可以得到两个数，hp[u]对应的插入数下标，ph[hp[b]],插入数下标对应的堆数组下标
void heap_swap(int a, int b) //要修改的两个堆数组下标，可得=> hp[a],hp[b] ,对应的插入数下标 => ph[hp[a]], ph[hp[b]] ,插入数对应的堆数组下标
{
    swap(h[a], h[b]); // 交换堆数组下标对应的值
    swap(hp[a], hp[b]);//插入数下标要跟着改变
    swap(ph[hp[a]], ph[hp[b]]); //堆数组下标是跟着插入数下标改变
}

void down(int u)// 下沉
{
    int t = u; // 存储值最小的结点的下标
    if (u * 2 <= siz && h[u * 2] < h[t]) t = u * 2;//比较左结点
    if (u * 2 + 1 <= siz && h[u * 2 + 1] < h[t]) t = u * 2 + 1;//比较右结点
    if (t != u)//不同，以为着左右子节点的值有更小的，那就交换
    {
        heap_swap(t, u);
        down(t);
    }
}
void up(int u)// 上浮
{
    while (u / 2 && h[u / 2] > h[u])//父节点存在且大于当前结点
    {
        heap_swap(u / 2, u);
        u = u / 2; //指向父节点，继续操作
    }
}
int main()
{
    int n;
    cin >> n;

    char op[10];
    int k, x;
    while (n -- )
    {
        scanf("%s", op);
        if (!strcmp(op, "I"))
        {
            scanf("%d", &x);
            siz ++ ;
            idx ++ ;
            h[siz] = x;
            ph[idx] = siz, hp[siz] = idx;
            up(siz);
        }
        else if (!strcmp(op, "PM"))
        {
            printf("%d\n", h[1]);
        }
        else if (!strcmp(op, "DM"))
        {
            heap_swap(1, siz);
            siz -- ;
            down(1);
        }
        else if (!strcmp(op, "D"))
        {
            scanf("%d", &k);
            k = ph[k];
            heap_swap(k, siz);
            siz -- ;
            down(k), up(k);
        }
        else
        {
            scanf("%d%d", &k, &x);
            k = ph[k];
            h[k] = x;
            down(k), up(k);
        }
    }

    return 0;
}