#include <bits/stdc++.h>
using namespace std;

const int N=1e5+5;
int A[N]; // 存储堆元素数组
int REC[N]; // 记录第k次插入堆中元素的下标i
int REV[N]; // 记录下标i的堆元素的插入次序k
int sz;

// 交换堆中元素
void heap_swap(int x, int y){
    swap(REC[REV[x]], REC[REV[y]]); // 交换索引
    swap(REV[x], REV[y]);
    swap(A[x], A[y]);
}


// sift down
void siftDown(int k){
    int index=k;
    if(2*k<=sz && A[2*k]<A[index]) index=2*k;
    if(2*k+1<=sz && A[2*k+1]<A[index]) index=2*k+1;
    if(index != k){
        heap_swap(index, k);
        siftDown(index);
    }
}

// sift up
void siftUp(int k){
    while(k/2 && A[k]<A[k/2]){
        heap_swap(k/2, k);
        k>>=1;
    }
}


int main(){
    // 模拟最小堆
    memset(A, 0x00, sizeof A);
    memset(REC, 0x00, sizeof REC);
    memset(REV, 0x00, sizeof REV);
    int n;
    cin>>n;
    sz=0; // 初始堆大小
    int order=0; // 记录当前是第几个插入的数
    while(n--){
        string P;
        int x, k;
        cin>>P;
        if(P=="I"){
            cin>>x;
            REC[++order]=++sz; // 第order次插入元素下标为sz
            REV[sz]=order; // 下标为sz的元是第order次插入
            A[sz]=x;
            siftUp(sz);
        }
        else if(P=="PM"){
            cout<<A[1]<<endl;
        }
        else if(P=="DM"){
            heap_swap(1, sz);
            sz--;
            siftDown(1);
        }
        else if(P=="D"){
            cin>>k;
            k=REC[k]; // 找到第k次插入的元素下标
            heap_swap(k, sz);
            sz--;
            siftUp(k);
            siftDown(k);
        }
        else if(P=="C"){
            cin>>k>>x;
            k=REC[k]; // 定位第k次插入元素的下标
            A[k]=x; // 修改改元素的值为x
            siftUp(k);
            siftDown(k);
        }
    }

    return 0;
}