← 返回题目列表

Codeforces · 681/C

C. 堆操作

中文机器翻译题面 查看原题

Petya 最近学习了名为“二叉堆”的数据结构。

他现在使用的堆允许执行以下操作:

- 将给定的数字放入堆中;
- 获取堆中最小元素的值;
- 从堆中提取最小元素;

因此,在任何时刻堆都包含多个整数(可能没有),其中一些可能是相等的。

为了更好地学习这个数据结构,Petya 拿了一个空堆并对其应用了上面的一些操作。此外,他还仔细地将所有操作及其结果记录到他的事件日志中,格式如下:

- insert x — 将值为 x 的元素放入堆中;
- getMin x — 堆中包含的最小元素的值等于 x;
- removeMin — 从堆中提取的最小元素(如果有多个实例,则仅提取一个实例)。

所有操作都是正确的,即每次应用 getMin 或 removeMin 操作时,堆中至少有一个元素。

当 Petya 外出吃午饭时,他的弟弟 Vova 来到房间,拿走了 Petya 日志中的一些页面并用它们制作纸船。

现在Vova担心他是否让Petya的操作顺序不一致。例如,如果按照事件日志中写入的顺序逐一应用操作,则 getMin 操作的结果可能与 Petya 记录的结果不同,并且某些 getMin 或 removeMin 操作可能不正确,因为应用时堆是空的。

现在Vova想要向事件日志中添加一些新的操作记录,以使结果操作顺序正确。也就是说,每次 getMin 操作的结果都等于记录中的结果,并且应用 getMin 和 removeMin 时堆非空。 Vova 希望尽快完成这件事,因为 Petya 随时可能回来。他要求你在当前日志中添加尽可能少的操作记录。请注意,可以在日志的开头、任意两个其他操作之间或日志的末尾添加任意数量的操作。

输入

输入的第一行包含唯一的整数 n (1 ≤ n ≤ 100 000) — Petya 日记中剩余的记录数。

以下 n 行中的每一行均按应用顺序描述当前日志中的记录。使用声明中描述的格式。输入中的所有数字均为绝对值不超过 109 的整数。

输出

输出的第一行应包含一个整数 m — 修改后的操作序列中可能的最小记录数。

接下来的 m 行应包含遵循输入格式(在语句中描述)的更正记录序列,每行一个并按照它们的应用顺序。输出中的所有数字均应为绝对值不超过 109 的整数。

请注意,操作的输入序列必须是输出序列的子序列。

保证存在包含不超过 1 000 000 次操作的正确答案。

示例

输入 #1

2
insert 3
getMin 4

输出 #1

4
insert 3
removeMin
insert 4
getMin 4

输入 #2

4
insert 1
insert 1
removeMin
getMin 2

输出 #2

6
insert 1
insert 1
removeMin
removeMin
insert 2
getMin 2

注意

在第一个样本中,将数字3插入堆后,最小数字为3。要使第一个getMin的结果等于4,应先从堆中删除数字3,然后将数字4添加到堆中。

在第二个示例案例中,编号 1 被插入两次,因此应类似地删除两次。