#include <iostream>
using namespace std;
const int N = 100010;
int h[N];
int findHead[N], findRank[N];
int n, num, id;
void head_swap(int u, int v){
    swap(h[u], h[v]);
    swap(findRank[u], findRank[v]);   // 交换插入次序
    swap(findHead[findRank[u]], findHead[findRank[v]]);   // 交换堆中的位置
}

void up(int u){
    while(u / 2 && h[u] < h[u / 2]){
        head_swap(u, u / 2);
        u /= 2;
    }
}
void down(int u){
    int t = u;
    if(u * 2 <= id && h[t] > h[2 * u])  t = u * 2;
    if(u * 2 + 1 <= id && h[t] > h[2 * u + 1])  t = u * 2 + 1;
    if(u != t){
        head_swap(t, u);
        down(t);
    }
}
int main(){
    cin >> n;
    string op;
    while(n -- ){
        cin >> op;
        if(op == "I"){
            int x;
            scanf("%d", &x);
            num ++ , id ++ ;
            h[id] = x;
            findRank[id] = num;
            findHead[num] = id;
            up(id);
        }else if(op == "PM")    cout << h[1] << endl;
        else if(op == "DM"){
            head_swap(1, id);
            id -- ;
            down(1);
        }else if(op == "D"){
            int k;
            scanf("%d", &k);
            int u = findHead[k];   // 找到在堆中的位置
            head_swap(u, id);      
            id -- ;
            down(u), up(u);
        }else{
            int k, x;
            scanf("%d%d", &k, &x);
            h[findHead[k]] = x;
            down(findHead[k]), up(findHead[k]);
        }
    }
    return 0;
}