Heap Operations

题意翻译

题目：堆的操作 题面： Petya近日学习了一种名为"二元堆"的数据结构。 这个数据结构支持以下操作： -将给定的数字放入堆中； -取得堆中最小的元素的值； -取出(去除)堆中最小的元素； 于是，这个堆在任何时候都包含数个整数(可能是一个)，它们当中有一些是相等的。 为了更好地学习这个数据结构，Petya创立了一个空的堆并在上面应用了一些操作。同时，他小心翼翼地在他的日志中写下了所有的操作，如下： insert x — 将一个值为x的元素插入堆中; getMin x — 这个时候，堆中最小的元素的值为x. removeMin — 移除堆中最小的元素(若有多个相同，只移除其中的一个). 所有的操作都是不矛盾的。换句话说，当应用 getMin 或者 removeMin 操作的时候，堆中有至少一个元素。 当Petya去吃午饭的时候，他的弟弟Vova进入了他的房间，拿走了Petya日志中的数页来做纸船。 现在Vova非常地焦虑，因为他可能已经让Petya的一系列操作变得前后矛盾。例如，如果一个一个地执行日志上所写着的操作，getMin操作所取得的结果可能与Petya记录的结果不同，而且如果这个时候堆是空的，那么 getMin 和 removeMin 操作将会产生错误。 Vova希望在日志中添加一些新的操作来让各项操作的结果正确。也就是说，每个 getMin 操作所得到的结果必须与日志中记录的相吻合，且不会出现操作前后矛盾或者导致错误。Vova想尽可能快地完成这些，因为Petya很快就会回来。现在Vova想要你在日志中添加尽可能少的操作纪录，这些记录可以被添加在日志的任何位置。 输入格式： 第一行一个整数n (1<=n<=100000) ，代表现在日志中剩余的操作数量。 接下来n行描述了现在日志中剩余的每一项操作，所有插入堆中的数的绝对值都不超过10^9. 输出格式： 输出的第一行应该输出一个单独的整数m，代表最小的更改后的日志文件包含的操作数量。 接下来m行输出更改后的正确日志，按顺序地每一行输出操作名称和参数或者得到的结果，所有输出的数字都应该是整数而且绝对值不大于10^9. 保证最后正确的操作序列日志中所包含的操作数量不大于1000000. 感谢@Mickey_snow 提供的翻译

题目描述

Petya has recently learned data structure named "Binary heap". The heap he is now operating with allows the following operations: - put the given number into the heap; - get the value of the minimum element in the heap; - extract the minimum element from the heap; Thus, at any moment of time the heap contains several integers (possibly none), some of them might be equal. In order to better learn this data structure Petya took an empty heap and applied some operations above to it. Also, he carefully wrote down all the operations and their results to his event log, following the format: - insert $ x $ — put the element with value $ x $ in the heap; - getMin $ x $ — the value of the minimum element contained in the heap was equal to $ x $ ; - removeMin — the minimum element was extracted from the heap (only one instance, if there were many). All the operations were correct, i.e. there was at least one element in the heap each time getMin or removeMin operations were applied. While Petya was away for a lunch, his little brother Vova came to the room, took away some of the pages from Petya's log and used them to make paper boats. Now Vova is worried, if he made Petya's sequence of operations inconsistent. For example, if one apply operations one-by-one in the order they are written in the event log, results of getMin operations might differ from the results recorded by Petya, and some of getMin or removeMin operations may be incorrect, as the heap is empty at the moment they are applied. Now Vova wants to add some new operation records to the event log in order to make the resulting sequence of operations correct. That is, the result of each getMin operation is equal to the result in the record, and the heap is non-empty when getMin ad removeMin are applied. Vova wants to complete this as fast as possible, as the Petya may get back at any moment. He asks you to add the least possible number of operation records to the current log. Note that arbitrary number of operations may be added at the beginning, between any two other operations, or at the end of the log.

输入输出格式

输入格式

The first line of the input contains the only integer $ n $ ( $ 1<=n<=100000 $ ) — the number of the records left in Petya's journal. Each of the following $ n $ lines describe the records in the current log in the order they are applied. Format described in the statement is used. All numbers in the input are integers not exceeding $ 10^{9} $ by their absolute value.

输出格式

The first line of the output should contain a single integer $ m $ — the minimum possible number of records in the modified sequence of operations. Next $ m $ lines should contain the corrected sequence of records following the format of the input (described in the statement), one per line and in the order they are applied. All the numbers in the output should be integers not exceeding $ 10^{9} $ by their absolute value. Note that the input sequence of operations must be the subsequence of the output sequence. It's guaranteed that there exists the correct answer consisting of no more than $ 1000000 $ operations.

输入输出样例

输入样例 #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

说明

In the first sample, after number $ 3 $ is inserted into the heap, the minimum number is $ 3 $ . To make the result of the first getMin equal to $ 4 $ one should firstly remove number $ 3 $ from the heap and then add number $ 4 $ into the heap. In the second sample case number $ 1 $ is inserted two times, so should be similarly removed twice.