#include<iostream>
using namespace std;
const int N = 100010;
int h[N];
int ph[N], hp[N];
int r = 0;
int idx = 0;
int x, k;
string opt;

void heap_swap(int x, int y) {
    swap(ph[hp[x]], ph[hp[y]]);
    swap(hp[x], hp[y]);
    swap(h[x], h[y]);
}

void down(int u) {
    int t = u;
    if (u * 2 <= r && h[t] > h[u * 2]) t = u * 2;
    if (u * 2 + 1 <= r && h[t] > h[u * 2 + 1]) t = u * 2 + 1;
    if (t != u) {
        heap_swap(u, t);
        down(t);
    }
}

void up(int u) {
    while (u / 2 >= 1  && h[u / 2] > h[u]) {
        heap_swap(u, u / 2);
        u /= 2;
    }
}

int main() {
    int m;
    cin >> m;
    while (m --) {
        cin >> opt;
        if (opt == "I") {//插入一个数x
            cin >> x;
            r  ++ ;
            idx ++ ;
            ph[idx] = r;
            hp[r] = idx;
            h[r] = x;
            up(r);
        }

        if (opt == "PM")  cout << h[1] << endl;//输出最小值

        if (opt == "DM") {//删除最小值
            heap_swap(1, r);
            r -- ;
            down(1);
        }

        if (opt == "D") {//删除第k个数
            cin >> k;
            k = ph[k];
            heap_swap(k, r);
            r -- ;
            down(k), up(k);
        }

        if (opt == "C") {//修改第k个数
            cin >> k >> x;
            k = ph[k];
            h[k] = x;
            down(k), up(k);
        }
    }

}