Heap

// ---------------------------- 堆 --------------------------------

// 1.插入一个数 heap[ ++ size] = x; up(size);
// 2.求集合当中的最小值 heap[1];
// 3.删除最小值 heap[1] = heap[size]; szie -- ; down(1);
// 4.删除任意一个元素 heap[k] = heap[size]; size -- ; down(k); up(k);
// 5.修改任意一个元素 heap[k] = x; down(k); up(k);


// h[N]存储堆中的值, h[1]是堆顶，x的左儿子是2x, 右儿子是2x + 1
// ph[k]存储第k个插入的点在堆中的位置
// hp[k]存储堆中下标是k的点是第几个插入的


/*
const int N = 1e5+10;
int h[N], ph[N], hp[N], size;

// 交换两个点，及其映射关系
void heap_swap(int a, int b)
{
    swap(ph[hp[a]],ph[hp[b]]);
    swap(hp[a], hp[b]);
    swap(h[a], h[b]);
}

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

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

// O(n)建堆
for (int i = n / 2; i; i -- ) down(i);

*/

// --------------------- 模拟堆 --------------------------

#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl '\n'

const int N = 1e5+10;

int h[N], siz, ph[N], hp[N];
int cnt;

inline void heap_swap(int a, int b)
{
    swap(ph[hp[a]],ph[hp[b]]);
    swap(hp[a], hp[b]);
    swap(h[a], h[b]);
}
inline void up(int u)
{
    while (u/2 && h[u] < h[u/2])
    {
        heap_swap(u, u/2);
        u >>= 1;
    }
}
inline 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);
    }
}
inline void insert(int x)
{
    h[++siz] = x;
    ph[++cnt] = siz;
    hp[siz] = cnt;
    up(siz);
}
inline void Delete(int u)
{
    int t = u;
    heap_swap(u, siz--);
    down(t); up(t);
}

inline void solve()
{
    int n; cin >> n;
    while (n--)
    {
        string s; cin >> s;
        if (s == "I")
        {
            int x; cin >> x;
            insert(x);
        }
        else if (s == "PM") cout << h[1] << endl;
        else if (s == "DM") Delete(1);
        else if (s == "D")
        {
            int k; cin >> k;
            Delete(ph[k]);
        }
        else if (s == "C")
        {
            int k, x; cin >> k >> x;
            h[ph[k]] = x; down(ph[k]); up(ph[k]);
        }
    }
}
signed main()
{
    IOS
    solve();
    return 0;
}