C. Операции с кучей
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Недавно Петя начал изучать структуру данных «Двоичная куча».

Куча, с которой он работает, позволяет выполнять следующие операции:

  • добавить число в кучу;
  • узнать минимальное число в куче;
  • удалить минимальное число из кучи.

Таким образом, в любой момент куча содержит в себе набор чисел (возможно, пустой), среди которых, возможно, есть одинаковые.

Чтобы лучше запомнить материал, Петя взял пустую кучу и стал применять к ней различные операции. Он не хотел ничего упустить, поэтому все выполненные операции он аккуратно записывал в журнал в порядке их выполнения, соблюдая следующий формат:

  • insert x — в кучу было добавлено число x;
  • getMin x — был выполнен запрос минимума, результатом запроса было число x;
  • removeMin — из кучи было удалено текущее минимальное число (только одно вхождение).

Последовательность операций была корректной, то есть на момент выполнения операций getMin и removeMin в куче находился хотя бы один элемент.

Пока Петя обедал, его младший брат Вова забежал к нему в комнату и вырвал из журнала несколько случайных страниц, так как ему не из чего было строить бумажные кораблики.

В какой-то момент Вова понял, что Петина последовательность операций могла стать некорректной. Например, если выполнять оставшиеся операции в том же порядке, в каком они были записаны, то результат операций getMin может не совпадать с результатом, записанным в журнале, а какие-то из операций getMin и removeMin вообще не могут быть выполнены, так как на момент их выполнения куча пуста.

Теперь Вове нужно дописать в произвольные места в журнале какие-нибудь операции так, чтобы последовательность снова стала корректной, то есть чтобы результат всех операций getMin совпадал с результатом, записанным в журнале, и все операции могли быть корректно выполнены. Вова хочет сделать это как можно быстрее, пока Петя не вернулся с обеда, то есть дописать в журнал минимально возможное количество операций. Любую операцию разрешается дописывать в начало последовательности, между любыми двумя операциями или в конец последовательности операций.

Помогите Вове решить эту проблему.

Входные данные

В первой строке входных данных записано число n (1 ≤ n ≤ 100 000) — количество записей, оставшихся в журнале Пети.

В каждой из следующих n строк записана одна из оставшихся в журнале записей об операциях с кучей в формате, описанном выше. Все числа во входных данных целые и не превышают 109 по абсолютной величине.

Выходные данные

В первой строке выведите целое число m — минимальное количество операций в исправленной последовательности.

В следующих m строках выведите эту последовательность операций по одной операции в каждой строке в формате, описанном выше. Все числа должны быть целыми и не превышать 109 по абсолютной величине.

Обратите внимание, что исправленная последовательность должна содержать в себе последовательность операций из входных данных в качестве подпоследовательности.

Гарантируется, что существует корректная последовательность операций, длина которой не превосходит 1 000 000.

Примеры
Входные данные
2
insert 3
getMin 4
Выходные данные
4
insert 3
removeMin
insert 4
getMin 4
Входные данные
4
insert 1
insert 1
removeMin
getMin 2
Выходные данные
6
insert 1
insert 1
removeMin
removeMin
insert 2
getMin 2
Примечание

В первом примере после добавления в кучу числа 3 минимумом будет являться единственное число 3, и для того, чтобы результатом операции getMin было число 4, нужно удалить из кучи 3 (как минимум) и затем добавить 4.

Во втором примере число 1 добавляется дважды, и удалить его нужно также дважды.