//idx第k个插入
let idx = 0, size = 0;
//从1开始
let heap = new Int32Array(500010);
let ph = new Int32Array(500010); //表示第k个插入的点在heap中的下标
let hp = new Int32Array(500010); //表示heap中的每个下标对应的第k个点
//这样存的原因:插入时,我们很容易通过ph就可以记录第k个插入点对应的heap下标,
//但是down/up交换时,我们传入的是heap下标,想要通过heap下标找到对应的第k个插入点,就必须遍历整个ph
//通过hp来存放heap下标对ph的映射关系,可以方便找到heap中的下标对应第几个插入的点
let swap = (arr, a, b) => {
let t = arr[a];
arr[a] = arr[b];
arr[b] = t;
}
let heapSwap = (a, b) => {
swap(ph, hp[a], hp[b]);//hp作用体现在这里
swap(hp, a, b);
swap(heap, a, b);
}
let down = a => {
let t = a, l = a * 2, r = a * 2 + 1;
if (l <= size && heap[l] < heap[t]) t = l;
if (r <= size && heap[r] < heap[t]) t = r;
if (t !== a) heapSwap(t, a), down(t);
};
let up = a => {
while (a > 1) {
let t = parseInt(a / 2);
if (heap[a] < heap[t]) heapSwap(a, t), a = t;
else return;
}
}
let insert = x => {
//插入 把新元素放末尾 up
heap[++size] = x;
ph[++idx] = size;
hp[size] = idx;
up(size);
}
let removeTop = () => {
//顶部与末尾交换后 size-- down
heapSwap(1, size--);
down(1);
}
let remove = k => {
//找到它在堆中的坐标与末尾交换 size-- down/up
let i = ph[k];
heapSwap(i, size--);
up(i), down(i); //down与up互斥
}
let modify = (k, x) => {
//找到它在堆中的坐标 修改值 down/up
let i = ph[k];
heap[i] = x;
up(i), down(i);
}
let buf = '';
process.stdin.on('readable', function () {
let chunk = process.stdin.read();
if (chunk) buf += chunk.toString();
});
let getInputNums = line => line.split(' ').filter(s => s !== '').map(x => parseInt(x));
let getInputStr = line => line.split(' ').filter(s => s !== '');
process.stdin.on('end', function () {
let m = 0;
buf.split('\n').forEach(function (line, lineIdx) {
if (lineIdx === 0) {
let a = getInputNums(line);
m = a[0];
} else if (lineIdx <= m) {
switch (line.slice(0, 2)) {
case 'I ': {
let arr = getInputNums(line.slice(2));
insert(arr[0]);
break;
}
case 'PM': {
console.log(heap[1]);
break;
}
case 'DM': {
removeTop();
break;
}
case 'D ': {
let arr = getInputNums(line.slice(2));
remove(arr[0]);
break;
}
case 'C ': {
let arr = getInputNums(line.slice(2));
modify(arr[0], arr[1]);
break;
}
}
}
});
});