#一维数组存一个数，左儿子是2x 右儿子2x+1 root 从 1 开始比较方便 要是从0 开始 2x = 0 冲突
# 插入一个数：         heap[++size] = x;  up(size)
# 求集合当中最小的值：  heap[1]
# 删除最小值：         heap[1] = heap[size]; size--; down[1]
# 删除任意一个元素     heap[k] = heap[size]; size --; down[k]; up[k]; (只会执行一个)
# 修改任意一个元素     heap[k] = x; down[k]; up[k];

def heap_swap(a,b):
    ph[hp[a]],ph[hp[b]] = ph[hp[b]],ph[hp[a]]               #交换ph查找的值（也就是在堆中对应值的下标）
    hp[a],hp[b] = hp[b],hp[a]                               #因为ph交换了 对应 hp也要交换
    h[a],h[b] = h[b],h[a]                                   #交换数值

def down(u):

    t = u                                                   # t —> temporary t存储较小的子节点下标
    if u * 2 <= size and h[u*2] < h[t]: t = u * 2           #与左儿子比较大小
    if u * 2 + 1 <= size and h[u*2+1] < h[t]: t = u * 2 + 1 #与右儿子比较大小

    if u != t:                                              #如果不等 说明儿子节点值比较小 可以向下down
        heap_swap(u,t)                              #要down的节点和较小子节点交换数值
        down(t)                                             #交换后继续检查是否能down

def up(u):

    while u//2 and h [u // 2] > h [u]:                      #跟父节点交换 直到父节点小于等于此节点
        heap_swap(u//2,u)
        u//=2


if __name__ == "__main__":
    N = 100010
    n = int(input())
    h = [0] * N
    size = 0
    m = 0
    ph,hp = [0]*(N),[0]*(N)                             # ph -> put heap ph[k]储存第k个插入的数在堆中的下标  hp[a]储存的是 a是第几个插入的 ph hp 互查

    for i in range(n):
        s = input()
        op = s[0:2]
        if op == 'I ':
            x = int(s[2:])
            size += 1
            m += 1
            ph[m], hp[size] = size, m
            h[size] = x
            up(size)


        elif op == 'D ':
            k = int(s[2:])
            k = ph[k]
            heap_swap(k,size)
            size -= 1
            down(k)
            up(k)

        elif op == 'C ':
            k,x = map(int,s[2:].split())
            k = ph[k]
            h[k] = x
            down(k)
            up(k)

        elif op == 'PM':
            print(h[1])

        elif op == 'DM':
            heap_swap(1,size)
            size -=1
            down(1)