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.


-----Input-----

The first line of the input contains the only integer n (1 ≤ n ≤ 100 000) — 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.


-----Output-----

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 1 000 000 operations.


-----Examples-----
Input
2
insert 3
getMin 4

Output
4
insert 3
removeMin
insert 4
getMin 4

Input
4
insert 1
insert 1
removeMin
getMin 2

Output
6
insert 1
insert 1
removeMin
removeMin
insert 2
getMin 2



-----Note-----

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.

Difficulty: MEDIUM_HARD
Tags: Greedy algorithms

Data structures

Constructive algorithms
Skill types: Data structures

Greedy algorithms

Starter code:

Solutions:
import math, sys
from collections import defaultdict, deque
import bisect as bi

def yes():
	print('YES')

def no():
	print('NO')

def I():
	return int(sys.stdin.readline())

def In():
	return map(int, sys.stdin.readline().split())

def Sn():
	return sys.stdin.readline().strip()
from heapq import heapify, heappop, heappush

def dict(a):
	d = {}
	for x in a:
		if d.get(x, -1) != -1:
			d[x] += 1
		else:
			d[x] = 1
	return d

def find_gt(a, x):
	i = bi.bisect_left(a, x)
	if i != len(a):
		return i
	else:
		return -1

def main():
	try:
		hp = []
		n = I()
		l = []
		for i in range(n):
			s = Sn()
			if s == 'removeMin':
				a = s
			else:
				(a, b) = s.split()
				b = int(b)
			if a == 'insert':
				heappush(hp, b)
				l.append((a, b))
			elif a == 'removeMin':
				if len(hp):
					heappop(hp)
				else:
					l.append(('insert', 1))
				l.append((a, ''))
			else:
				while len(hp) and hp[0] < b:
					l.append(('removeMin', ''))
					heappop(hp)
				if not len(hp):
					heappush(hp, b)
					l.append(('insert', b))
				elif len(hp) and hp[0] != b:
					heappush(hp, b)
					l.append(('insert', b))
				l.append((a, b))
		print(len(l))
		for x in l:
			sys.stdout.write(x[0] + ' ' + str(x[1]) + '\n')
	except:
		pass
M = 998244353
P = 1000000007
for _ in range(1):
	main()


from __future__ import print_function
from collections import *
from sys import stdin
from heapq import *
from math import *
g = lambda : stdin.readline().strip()
gl = lambda : g().split()
gil = lambda : [int(var) for var in gl()]
gfl = lambda : [float(var) for var in gl()]
gcl = lambda : list(g())
gbs = lambda : [int(var) for var in g()]
rr = lambda x: reversed(range(x))
mod = int(1000000000.0) + 7
inf = float('inf')
ans = []
h = []
for _ in range(gil()[0]):
	res = gl()
	if len(res) == 1:
		if h == []:
			ans.append('insert 1')
		ans.append(res[0])
		if h:
			heappop(h)
	elif res[0] == 'insert':
		ans.append(' '.join(res))
		heappush(h, int(res[1]))
	else:
		val = int(res[1])
		while h and h[0] < val:
			ans.append('removeMin')
			heappop(h)
		if len(h) == 0 or h[0] != val:
			ans.append('insert ' + res[1])
			heappush(h, val)
		ans.append(' '.join(res))
print(len(ans))
print('\n'.join(ans))


from heapq import heappush, heappop

def main():
	heap = []
	ans = []
	(n, hsize) = (int(input()), 0)
	for i in range(n):
		ss = input()
		if ss != 'removeMin':
			(a, bb) = ss.split()
			b = int(bb)
			if a == 'insert':
				hsize += 1
				heappush(heap, b)
			else:
				while hsize > 0 and heap[0] < b:
					ans += ['removeMin']
					hsize -= 1
					heappop(heap)
				if hsize == 0 or heap[0] != b:
					ans += ['insert ' + bb]
					heappush(heap, b)
					hsize += 1
		elif hsize == 0:
			ans += ['insert 0']
		else:
			heappop(heap)
			hsize -= 1
		ans += [ss]
	print(len(ans))
	print('\n'.join(ans))

def __starting_point():
	main()
__starting_point()


def main():
	from heapq import heappop, heappush
	from sys import stdin
	(h, res) = ([], [])
	for _ in range(int(input())):
		s = input()
		if s == 'removeMin':
			if h:
				heappop(h)
			else:
				res.append('insert 1')
		else:
			(c, x) = s.split()
			x = int(x)
			if c == 'insert':
				heappush(h, x)
			else:
				while h and h[0] < x:
					heappop(h)
					res.append('removeMin')
				if not h or h[0] > x:
					heappush(h, x)
					res.append('insert %d' % x)
		res.append(s)
	print(len(res))
	print('\n'.join(res))
main()


def go():
	from sys import stdin
	from heapq import heappush, heappop
	b = 0
	p = []
	res = []
	(n, *L) = stdin.read().splitlines()
	n = int(n)
	for x in L:
		a = x.split()
		if a[0][0] == 'r':
			if not p:
				res.append('insert 45')
			else:
				heappop(p)
		elif a[0][0] == 'g':
			b = int(a[1])
			while p and p[0] < b:
				res.append('removeMin')
				heappop(p)
			if not p or p[0] > b:
				res.append('insert ' + a[1])
				heappush(p, b)
		else:
			heappush(p, int(a[1]))
		res.append(x)
	print(len(res))
	print('\n'.join(res))
go()


from sys import stdin
import heapq

def process_input(iarr):
	oarr = []
	myheap = []
	heapq.heapify(myheap)
	for i in range(len(iarr)):
		if iarr[i][0] == 1:
			heapq.heappush(myheap, iarr[i][1])
			oarr.append(iarr[i])
		elif iarr[i][0] == 2:
			if len(myheap) == 0 or myheap[0] > iarr[i][1]:
				heapq.heappush(myheap, iarr[i][1])
				oarr.append([1, iarr[i][1]])
				oarr.append(iarr[i])
			elif myheap[0] < iarr[i][1]:
				while len(myheap) > 0 and myheap[0] < iarr[i][1]:
					heapq.heappop(myheap)
					oarr.append([3, -1])
				if len(myheap) == 0 or myheap[0] > iarr[i][1]:
					heapq.heappush(myheap, iarr[i][1])
					oarr.append([1, iarr[i][1]])
				oarr.append(iarr[i])
			else:
				oarr.append(iarr[i])
				continue
		else:
			if len(myheap) == 0:
				heapq.heappush(myheap, 1)
				oarr.append([1, 1])
			heapq.heappop(myheap)
			oarr.append(iarr[i])
	return oarr
n = int(stdin.readline().strip())
iarr = []
for _ in range(n):
	inp = list(stdin.readline().split())
	if len(inp) == 2:
		inp[1] = int(inp[1])
		if inp[0] == 'insert':
			iarr.append([1, inp[1]])
		else:
			iarr.append([2, inp[1]])
	else:
		iarr.append([3, -1])
oarr = process_input(iarr)
print(len(oarr))
for i in range(len(oarr)):
	if oarr[i][0] == 1:
		print('insert', oarr[i][1])
	elif oarr[i][0] == 2:
		print('getMin', oarr[i][1])
	else:
		print('removeMin')


from heapq import heappush, heappop
n = int(input())
heap = []
res = []
for i in range(n):
	string = input()
	oper = string.split()
	if oper[0][0] == 'i':
		heappush(heap, int(oper[1]))
	elif oper[0][0] == 'g':
		key = int(oper[1])
		while heap and heap[0] < key:
			heappop(heap)
			res.append('removeMin')
		if not heap or heap[0] != key:
			heappush(heap, key)
			res.append('insert ' + oper[1])
	elif heap:
		heappop(heap)
	else:
		res.append('insert 0')
	res.append(string)
print(len(res))
print('\n'.join(res))


from heapq import *
n = int(input())
(q, ans, k) = ([], [], 0)
for i in range(n):
	ss = input()
	if ss != 'removeMin':
		(s, mm) = ss.split()
		m = int(mm)
		if s == 'insert':
			k += 1
			heappush(q, m)
		else:
			while k == 0 or q[0] != m:
				if k == 0:
					heappush(q, m)
					ans += ['insert ' + mm]
					k += 1
				elif q[0] < m:
					k -= 1
					t = heappop(q)
					ans += ['removeMin']
				else:
					k += 1
					heappush(q, m)
					ans += ['insert ' + mm]
	elif k == 0:
		ans += ['insert 1']
	else:
		heappop(q)
		k -= 1
	ans += [ss]
print(len(ans))
print('\n'.join(ans))


from heapq import *
n = int(input())
heap = []
ops = []
for i in range(n):
	ln = input().rstrip()
	if ln[0] == 'i':
		X = int(ln.split()[1])
		heappush(heap, X)
		ops.append(ln)
		continue
	if ln[0] == 'g':
		X = int(ln.split()[1])
		while heap and heap[0] < X:
			heappop(heap)
			ops.append('removeMin')
		if not heap or heap[0] > X:
			ops.append('insert ' + str(X))
			heappush(heap, X)
		ops.append(ln)
		continue
	if not heap:
		ops.append('insert 1')
	else:
		heappop(heap)
	ops.append(ln)
print(len(ops))
print('\n'.join(ops))


from heapq import *
numLines = int(input())
heap = []
output_ops = []
for _ in range(numLines):
	opString = input()
	operation = opString.split()
	if operation[0] == 'insert':
		heappush(heap, int(operation[1]))
	if operation[0] == 'removeMin':
		if not heap:
			heappush(heap, 1)
			output_ops.append('insert 1')
		heappop(heap)
	elif operation[0] == 'getMin':
		currMin = int(operation[1])
		while heap and heap[0] < currMin:
			heappop(heap)
			output_ops.append('removeMin')
		if not heap or heap[0] > currMin:
			heappush(heap, currMin)
			output_ops.append('insert ' + str(currMin))
	output_ops.append(opString)
print(len(output_ops))
for op in output_ops:
	print(op)


import math
import sys
import heapq
input = sys.stdin.readline

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input().strip()
	return list(s[:len(s)])

def invr():
	return map(int, input().split())
n = inp()
l = []
a = []
heapq.heapify(l)
count_ex = 0
for i in range(n):
	x = input()
	cm = x.split()
	if cm[0] == 'insert':
		v = int(cm[1])
		heapq.heappush(l, v)
	elif cm[0] == 'removeMin':
		if len(l) == 0:
			a.append('insert 0')
		else:
			heapq.heappop(l)
	else:
		v = int(cm[1])
		while len(l) > 0 and l[0] != v:
			if l[0] < v:
				a.append('removeMin')
				heapq.heappop(l)
			else:
				a.append('insert {}'.format(v))
				heapq.heappush(l, v)
		if len(l) == 0:
			a.append('insert {}'.format(v))
			heapq.heappush(l, v)
	a.append(x)
print(len(a))
for each in a:
	print(each.strip())


from sys import stdin, stdout

def siftup(ind):
	while ind != 1 and heap[ind] < heap[ind // 2]:
		(heap[ind], heap[ind // 2]) = (heap[ind // 2], heap[ind])
		ind //= 2

def siftdown(ind):
	while len(heap) > ind * 2 + 1 and (heap[ind] > heap[ind * 2] or heap[ind] > heap[ind * 2 + 1]):
		if heap[ind * 2 + 1] < heap[ind * 2]:
			(heap[ind], heap[ind * 2 + 1]) = (heap[ind * 2 + 1], heap[ind])
			ind = ind * 2 + 1
		else:
			(heap[ind], heap[ind * 2]) = (heap[ind * 2], heap[ind])
			ind = ind * 2
	if len(heap) > ind * 2 and heap[ind] > heap[ind * 2]:
		(heap[ind], heap[ind * 2]) = (heap[ind * 2], heap[ind])
		ind *= 2
n = int(stdin.readline())
heap = [0]
steps = []
for i in range(n):
	s = stdin.readline().rstrip().split()
	if s.count('insert'):
		heap.append(int(s[-1]))
		siftup(len(heap) - 1)
		steps.append(' '.join(s))
	elif s.count('getMin'):
		while len(heap) != 1 and heap[1] < int(s[-1]):
			steps.append('removeMin')
			if len(heap) == 2:
				heap.pop()
			else:
				heap[1] = heap[-1]
				heap.pop()
				siftdown(1)
		if len(heap) > 1 and heap[1] != int(s[-1]):
			steps.append(' '.join(['insert'] + [s[-1]]))
			heap.append(int(s[-1]))
			siftup(len(heap) - 1)
		elif len(heap) == 1:
			steps.append(' '.join(['insert'] + [s[-1]]))
			heap.append(int(s[-1]))
		steps.append(' '.join(s))
	elif len(heap) > 1:
		steps.append(' '.join(s))
		if len(heap) > 2:
			heap[1] = heap[-1]
			heap.pop()
			siftdown(1)
		else:
			heap.pop()
	else:
		steps.append(' '.join(['insert', '1']))
		steps.append('removeMin')
stdout.write(str(len(steps)) + '\n')
for i in range(len(steps)):
	stdout.write(steps[i] + '\n')


from heapq import heappop, heappush
from sys import stdin
(n, *l) = stdin.read().splitlines()
(heap, res) = ([], [])
for s in l:
	array = s.split()
	if array[0] == 'insert':
		heappush(heap, int(array[1]))
	elif array[0] == 'getMin':
		key = int(array[1])
		while heap and heap[0] < key:
			heappop(heap)
			res.append('removeMin')
		if not heap or heap[0] != key:
			heappush(heap, key)
			res.append('insert ' + array[1])
	elif heap:
		heappop(heap)
	else:
		res.append('insert 0')
	res.append(s)
print(len(res))
print('\n'.join(res))


from heapq import heappop, heappush
from sys import stdin
input = stdin.readline
res = []
l = 0
q = []
for _ in range(int(input())):
	a = input()
	if a[:6] == 'insert':
		heappush(q, int(a.split()[1]))
	elif a[:6] == 'getMin':
		mn = int(a.split()[1])
		while q and q[0] < mn:
			res.append('removeMin')
			heappop(q)
			l += 1
		if not q or q[0] > mn:
			res.append('insert ' + str(mn))
			heappush(q, mn)
			l += 1
	elif q:
		heappop(q)
	else:
		res.append('insert 0')
		l += 1
	res.append(a)
	l += 1
print(l)
print('\n'.join(res))


from sys import stdin
input = stdin.readline
from heapq import heappop, heappush
n = int(input())
arr = [input() for _ in range(n)]
(res, q) = ([], [])
for s in arr:
	if s[0] == 'i':
		heappush(q, int(s.split()[1]))
	elif s[0] == 'g':
		val = int(s.split()[1])
		while q and q[0] < val:
			res.append('removeMin')
			heappop(q)
		if not q or q[0] > val:
			res.append('insert ' + s.split()[1])
			heappush(q, val)
	elif q:
		heappop(q)
	else:
		res.append('insert 1')
	res.append(s)
print(len(res))
print('\n'.join(res))


from sys import stdin
from heapq import heappush, heappop
(n, *L) = stdin.read().splitlines()
heap = []
res = []
for string in L:
	oper = string.split()
	if oper[0][0] == 'i':
		heappush(heap, int(oper[1]))
	elif oper[0][0] == 'g':
		key = int(oper[1])
		while heap and heap[0] < key:
			heappop(heap)
			res.append('removeMin')
		if not heap or heap[0] != key:
			heappush(heap, key)
			res.append('insert ' + oper[1])
	elif heap:
		heappop(heap)
	else:
		res.append('insert 0')
	res.append(string)
print(len(res))
print('\n'.join(res))


import heapq
n = int(input())
m = n
ans = []
myheap = []
for i in range(n):
	s = input()
	command = s.split()
	if command[0] == 'insert':
		heapq.heappush(myheap, int(command[1]))
	elif command[0] == 'removeMin':
		if myheap:
			heapq.heappop(myheap)
		else:
			m += 1
			ans.append('insert 1')
	elif command[0] == 'getMin':
		num = int(command[1])
		while myheap:
			if myheap[0] < num:
				m += 1
				ans.append('removeMin')
				heapq.heappop(myheap)
			else:
				break
		else:
			m += 1
			ans.append('insert ' + str(num))
			heapq.heappush(myheap, num)
		if myheap[0] > num:
			m += 1
			ans.append('insert ' + str(num))
			heapq.heappush(myheap, num)
	ans.append(s)
print(m)
print('\n'.join(ans))


import heapq
n = int(input())
m = n
(ans, hp_dgt) = ([], [])
for i in range(n):
	s = input()
	a = s.split()
	if a[0] == 'insert':
		heapq.heappush(hp_dgt, int(a[1]))
	elif a[0] == 'removeMin':
		if hp_dgt:
			heapq.heappop(hp_dgt)
		else:
			m += 1
			ans.append('insert 1')
	elif a[0] == 'getMin':
		x = int(a[1])
		while hp_dgt:
			if hp_dgt[0] < x:
				m += 1
				ans.append('removeMin')
				heapq.heappop(hp_dgt)
			else:
				break
		else:
			m += 1
			ans.append('insert ' + str(x))
			heapq.heappush(hp_dgt, x)
		if hp_dgt[0] > x:
			m += 1
			ans.append('insert ' + str(x))
			heapq.heappush(hp_dgt, x)
	ans.append(s)
print(m)
print('\n'.join(ans))


from __future__ import division, print_function
import heapq
import math
import sys
import os
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())
n = inp()
l = []
a = []
heapq.heapify(l)
count_ex = 0
for i in range(n):
	x = input()
	cm = x.split()
	if cm[0] == 'insert':
		v = int(cm[1])
		heapq.heappush(l, v)
	elif cm[0] == 'removeMin':
		if len(l) == 0:
			a.append('insert 0')
		else:
			heapq.heappop(l)
	else:
		v = int(cm[1])
		while len(l) > 0 and l[0] != v:
			if l[0] < v:
				a.append('removeMin')
				heapq.heappop(l)
			else:
				a.append('insert {}'.format(v))
				heapq.heappush(l, v)
		if len(l) == 0:
			a.append('insert {}'.format(v))
			heapq.heappush(l, v)
	a.append(x)
print(len(a))
for each in a:
	print(each.strip())


import heapq
n = int(input())
commands = []
arr = []
for i in range(n):
	s = input()
	tmp = s.split(' ')
	if tmp[0] == 'insert':
		heapq.heappush(arr, int(tmp[1]))
	elif tmp[0] == 'removeMin':
		if not len(arr):
			commands.append('insert 1')
		else:
			heapq.heappop(arr)
	else:
		x = int(tmp[1])
		while len(arr) and arr[0] < x:
			commands.append('removeMin')
			heapq.heappop(arr)
		if not len(arr) or arr[0] != x:
			commands.append('insert ' + tmp[1])
			heapq.heappush(arr, x)
	commands.append(s)
print(len(commands))
print('\n'.join(commands))


from heapq import *
ans = []
fin = []
import sys
input = sys.stdin.readline
a = int(input())
arr = [input() for i in range(a)]
for s in arr:
	if s[0] == 'r':
		if len(ans) == 0:
			fin.append('insert 1')
		else:
			heappop(ans)
	elif s[0] == 'i':
		heappush(ans, int(s.split()[1]))
	elif s[0] == 'g':
		val = int(s.split()[1])
		while ans and ans[0] < val:
			heappop(ans)
			fin.append('removeMin')
		if len(ans) == 0 or ans[0] > val:
			fin.append('insert ' + s.split()[1])
			heappush(ans, val)
	fin.append(s)
print(len(fin))
for i in range(len(fin)):
	print(fin[i])


import heapq
m = int(input())
heap = []
ans = []
for i in range(m):
	a = input()
	if a == 'removeMin':
		if heap == []:
			heapq.heappush(heap, 1)
			heapq.heappop(heap)
			ans.append('insert 1')
			ans.append('removeMin')
		else:
			heapq.heappop(heap)
			ans.append('removeMin')
	else:
		(a, x) = a.split()
		x = int(x)
		if a == 'insert':
			heapq.heappush(heap, x)
			ans.append('insert ' + str(x))
		else:
			while len(heap) > 0 and heap[0] < x:
				heapq.heappop(heap)
				ans.append('removeMin')
			if len(heap) > 0 and heap[0] == x:
				ans.append('getMin ' + str(x))
			else:
				heapq.heappush(heap, x)
				ans.append('insert ' + str(x))
				ans.append('getMin ' + str(x))
print(len(ans))
print('\n'.join(ans))


import heapq
n = int(input())
m = n
operations = []
heap = []
for i in range(n):
	s = input()
	a = s.split()
	if a[0] == 'insert':
		heapq.heappush(heap, int(a[1]))
	elif a[0] == 'removeMin':
		if heap:
			heapq.heappop(heap)
		else:
			m += 1
			operations.append('insert 1')
	elif a[0] == 'getMin':
		b = int(a[1])
		while heap:
			if heap[0] < b:
				operations.append('removeMin')
				m += 1
				heapq.heappop(heap)
			else:
				break
		else:
			operations.append('insert {}'.format(b))
			m += 1
			heapq.heappush(heap, b)
		if heap[0] > b:
			operations.append('insert {}'.format(b))
			m += 1
			heapq.heappush(heap, b)
	operations.append(s)
print(m)
print('\n'.join(operations))


import sys
from heapq import *
answer = []
n = int(input())

def main():
	h = []
	all_input = sys.stdin.readlines()
	for q in all_input:
		raw = q.split()
		if raw[0] == 'insert':
			v = int(raw[1])
			heappush(h, v)
		elif raw[0] == 'getMin':
			v = int(raw[1])
			while h and h[0] < v:
				answer.append('removeMin\n')
				heappop(h)
			if not h or h[0] > v:
				answer.append('insert ' + raw[1] + '\n')
				heappush(h, v)
		elif h:
			heappop(h)
		else:
			answer.append('insert 0\n')
		answer.append(q)

def print_answer():
	print(len(answer))
	print(''.join(answer))
main()
print_answer()


from heapq import heappush, heappop
import sys
inp = sys.stdin.readline

def main():
	heap = []
	ans = []
	n = int(inp())
	for i in range(n):
		ss = inp()
		if ss != 'removeMin\n':
			(a, bb) = ss.split()
			b = int(bb)
			if a == 'insert':
				heappush(heap, b)
			else:
				while heap and heap[0] < b:
					ans += ['removeMin\n']
					heappop(heap)
				if not heap or heap[0] != b:
					ans += ['insert %s\n' % bb]
					heappush(heap, b)
		elif not heap:
			ans += ['insert 0\n']
		else:
			heappop(heap)
		ans += [ss]
	print(len(ans))
	print(''.join(ans))
main()


from collections import *
import sys
input = sys.stdin.readline
import heapq

def ri():
	return int(input())

def rl():
	return list(map(int, input().split()))
n = ri()
hh = []
heapq.heapify(hh)
out = []
for i in range(n):
	current_input = input().strip('\n')
	instruction = current_input.split()
	if len(instruction) > 1:
		instruction[1] = int(instruction[1])
		if instruction[0] == 'insert':
			heapq.heappush(hh, instruction[1])
			out.append(current_input)
		else:
			mini = instruction[1]
			while hh and hh[0] < mini:
				out.append('removeMin')
				heapq.heappop(hh)
			if not hh or hh[0] > mini:
				heapq.heappush(hh, mini)
				out.append('insert ' + str(mini))
			out.append(current_input)
	else:
		if len(hh) == 0:
			out.append('insert 1')
			heapq.heappush(hh, 1)
		out.append('removeMin')
		heapq.heappop(hh)
print(len(out))
for o in out:
	print(o)


import math, heapq
import sys
input = sys.stdin.readline
n = int(input())
flag = 0
ans = []
l = []
heapq.heapify(l)
for i in range(n):
	s = input()
	if s[0] == 'i':
		heapq.heappush(l, int(s[7:len(s) - 1]))
		ans.append(s[0:len(s) - 1])
		continue
	if s[0] == 'r':
		if len(l) == 0:
			ans.append('insert 1')
			ans.append(s[0:len(s) - 1])
		else:
			ans.append(s[0:len(s) - 1])
			heapq.heappop(l)
		continue
	val = int(s[7:len(s) - 1])
	f = 0
	while len(l) > 0 and f == 0:
		if val == l[0]:
			f = 1
			break
		if val > l[0]:
			heapq.heappop(l)
			ans.append('removeMin')
			continue
		heapq.heappush(l, val)
		ans.append('insert ' + str(val))
		f = 1
		break
	if f == 0:
		heapq.heappush(l, val)
		ans.append('insert ' + str(val))
	ans.append(s[0:len(s) - 1])
print(len(ans))
for i in ans:
	print(i)


from sys import stdin
from bisect import bisect_left
n = int(stdin.readline())
heap = []
res = []
for i in range(n):
	string = stdin.readline()
	oper = string.split()
	if oper[0][0] == 'i':
		key = int(oper[1])
		pos = bisect_left(heap, key)
		heap[pos:pos] = [key]
	elif oper[0][0] == 'g':
		key = int(oper[1])
		num = bisect_left(heap, key)
		heap[:num] = []
		res.extend(['removeMin\n'] * num)
		if not heap or heap[0] != key:
			heap[0:0] = [key]
			res.append('insert ' + oper[1] + '\n')
	elif heap:
		heap[:1] = []
	else:
		res.append('insert 0\n')
	res.append(string)
print(len(res))
print(''.join(res), end='')


import sys

def insert(heap, val):
	idx = len(heap)
	heap.append(val)
	while idx > 0:
		p = idx - 1 >> 1
		if heap[p] <= heap[idx]:
			break
		(heap[p], heap[idx]) = (heap[idx], heap[p])
		idx = p

def removeMin(heap):
	last = heap.pop()
	L = len(heap)
	if L == 0:
		return
	heap[0] = last
	idx = 0
	while True:
		l = (idx << 1) + 1
		if l >= L:
			return
		r = l + 1
		best = r if r < L and heap[r] < heap[l] else l
		if heap[best] >= heap[idx]:
			return
		(heap[best], heap[idx]) = (heap[idx], heap[best])
		idx = best
answer = []
n = int(input())

def main():
	h = []
	all_input = sys.stdin.readlines()
	for q in all_input:
		raw = q.split()
		if raw[0] == 'insert':
			v = int(raw[1])
			insert(h, v)
		elif raw[0] == 'getMin':
			v = int(raw[1])
			while h and h[0] < v:
				answer.append('removeMin\n')
				removeMin(h)
			if not h or h[0] > v:
				answer.append('insert ' + raw[1] + '\n')
				insert(h, v)
		elif h:
			removeMin(h)
		else:
			answer.append('insert 0\n')
		answer.append(q)

def print_answer():
	print(len(answer))
	print(''.join(answer))
main()
print_answer()


from heapq import heappop, heappush
n = int(input())
ans = []
q = []
for i in range(n):
	s = input()
	op = s.split()
	if op[0] == 'insert':
		heappush(q, int(op[1]))
	elif op[0] == 'removeMin':
		if len(q) > 0:
			heappop(q)
		else:
			ans.append('insert 1')
	else:
		val = int(op[1])
		while len(q) > 0 and q[0] < val:
			ans.append('removeMin')
			heappop(q)
		if len(q) == 0 or q[0] > val:
			ans.append('insert ' + op[1])
			heappush(q, val)
	ans.append(s)
print(len(ans))
print('\n'.join(ans))


from heapq import heappush, heappop
h = []
ans = []

def main():
	nonlocal h
	n = int(input())
	for i in range(n):
		s = input()
		if s[0] == 'i':
			data = int(s.split()[1])
			heappush(h, data)
			ans.append(s)
		elif s[0] == 'g':
			data = int(s.split()[1])
			while h and h[0] < data:
				heappop(h)
				ans.append('removeMin')
			if not h or h[0] > data:
				heappush(h, data)
				ans.append('insert ' + str(data))
			ans.append(s)
		else:
			if not h:
				ans.append('insert 0')
			else:
				heappop(h)
			ans.append('removeMin')
	print(len(ans))
	print('\n'.join(ans))

def __starting_point():
	main()
__starting_point()


from heapq import heapify, heappop, heappush
n = int(input())
a = []
fi = []
heapify(a)
for _ in range(0, n):
	s = input().split(' ')
	if s[0] == 'insert':
		heappush(a, int(s[1]))
		fi.append(' '.join(s))
	elif s[0] == 'getMin':
		while len(a) > 0 and a[0] < int(s[1]):
			fi.append('removeMin')
			heappop(a)
		if len(a) == 0:
			fi.append('insert ' + s[1])
			heappush(a, int(s[1]))
			fi.append(' '.join(s))
		else:
			if len(a) > 0 and a[0] > int(s[1]):
				fi.append('insert ' + s[1])
				heappush(a, int(s[1]))
			fi.append(' '.join(s))
	elif len(a) == 0:
		fi.append('insert 0')
		fi.append(' '.join(s))
	else:
		fi.append(' '.join(s))
		heappop(a)
print(len(fi))
for i in fi:
	print(i)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
n = int(input())
l = []
l1 = []
l2 = []
l3 = []
from heapq import heapify, heappush as hp, heappop as hpop
for i in range(n):
	l.append(input().split())
l = l[::-1]
ans = []
h = []
heapify(h)
while len(l):
	if l[-1][0] == 'insert':
		ans.append(l[-1])
		hp(h, int(l[-1][1]))
		l.pop()
	elif l[-1][0] == 'getMin':
		a = 10 ** 10
		if len(h):
			a = hpop(h)
			if a < int(l[-1][1]):
				ans.append(['removeMin'])
		if len(h):
			while a < int(l[-1][1]):
				if len(h) == 0:
					break
				a = hpop(h)
				if a < int(l[-1][1]):
					ans.append(['removeMin'])
		if a == 10 ** 10 or a < int(l[-1][1]):
			hp(h, int(l[-1][1]))
			ans.append(['insert', l[-1][1]])
			ans.append(l[-1])
			l.pop()
		elif a == int(l[-1][1]):
			ans.append(l[-1])
			l.pop()
			hp(h, a)
		elif a > int(l[-1][1]):
			hp(h, a)
			hp(h, int(l[-1][1]))
			ans.append(['insert', l[-1][1]])
			ans.append(l[-1])
			l.pop()
	elif len(h):
		ans.append(l[-1])
		hpop(h)
		l.pop()
	else:
		ans.append(['insert', '1'])
		ans.append(l[-1])
		l.pop()
print(len(ans))
for i in ans:
	print(*i)


import heapq
strList = []
heap = []
n = int(input())
while n > 0:
	command = input().split()
	num = len(heap)
	if command[0] == 'insert':
		strList.append(' '.join(command))
		heapq.heappush(heap, int(command[1]))
	elif command[0] == 'removeMin':
		if num == 0:
			strList.append('insert 0')
			heapq.heappush(heap, 0)
			strList.append('removeMin')
			heapq.heappop(heap)
		else:
			strList.append('removeMin')
			heapq.heappop(heap)
	elif num == 0:
		strList.append(f'insert {command[1]}')
		heapq.heappush(heap, int(command[1]))
		strList.append(' '.join(command))
	else:
		minHeap = heapq.heappop(heap)
		heapq.heappush(heap, minHeap)
		if minHeap == int(command[1]):
			strList.append(' '.join(command))
		elif minHeap > int(command[1]):
			strList.append(f'insert {command[1]}')
			heapq.heappush(heap, int(command[1]))
			strList.append(' '.join(command))
		else:
			inserted = int(command[1])
			while inserted > minHeap and len(heap) >= 1:
				minHeap = heapq.heappop(heap)
				if minHeap < inserted:
					strList.append('removeMin')
				else:
					heapq.heappush(heap, minHeap)
					break
			if minHeap > inserted or len(heap) == 0:
				strList.append(f'insert {inserted}')
				heapq.heappush(heap, inserted)
				strList.append(' '.join(command))
			elif minHeap == inserted:
				strList.append(' '.join(command))
	n -= 1
print(len(strList))
for item in strList:
	print(item)


import heapq
n = int(input())
heap = []
anss = []
for q in range(n):
	a = input()
	ans = a.split()
	if ans[0] == 'insert':
		heapq.heappush(heap, int(ans[1]))
	elif ans[0] == 'removeMin':
		if len(heap) > 0:
			heapq.heappop(heap)
		else:
			anss.append('insert 1')
	else:
		while len(heap) > 0 and heap[0] < int(ans[1]):
			heapq.heappop(heap)
			anss.append('removeMin')
		if len(heap) > 0 and heap[0] != int(ans[1]):
			heapq.heappush(heap, int(ans[1]))
			anss.append('insert ' + ans[1])
		elif len(heap) == 0:
			heapq.heappush(heap, int(ans[1]))
			anss.append('insert ' + ans[1])
	anss.append(a)
print(len(anss))
for i in anss:
	print(i)


import heapq as hq
heap = []
hq.heapify(heap)
ans = []
for _ in range(int(input())):
	s = input().split()
	if s[0] == 'insert':
		hq.heappush(heap, int(s[1]))
		ans.append('insert ' + s[1])
	elif s[0] == 'getMin':
		while len(heap) > 0 and heap[0] < int(s[1]):
			ans.append('removeMin')
			hq.heappop(heap)
		if len(heap) == 0 or heap[0] != int(s[1]):
			ans.append('insert ' + s[1])
			hq.heappush(heap, int(s[1]))
		ans.append('getMin ' + s[1])
	else:
		if len(heap) == 0:
			ans.append('insert 0')
		else:
			hq.heappop(heap)
		ans.append('removeMin')
print(len(ans))
print('\n'.join(ans))


import sys
from collections import defaultdict
from heapq import heappop, heappush

def main():
	n = int(sys.stdin.readline())
	h = []
	d = sys.stdin.readlines()
	res = []
	for i in range(n):
		x = d[i].split()
		if x[0] == 'insert':
			t = int(x[1])
			heappush(h, t)
		elif x[0] == 'getMin':
			t = int(x[1])
			while len(h) > 0 and h[0] < t:
				res.append('removeMin')
				heappop(h)
			if len(h) == 0 or h[0] > t:
				res.append('insert ' + x[1])
				heappush(h, t)
		elif x[0] == 'removeMin':
			if len(h) == 0:
				res.append('insert 0')
			else:
				heappop(h)
		res.append(d[i].rstrip())
	print(len(res))
	print('\n'.join(res))
main()


import heapq

def inp(n):
	L = []
	for i in range(n):
		s = str(input())
		s1 = s.split()
		if len(s1) == 2:
			L.append([s1[0], int(s1[1])])
		else:
			L.append(s1)
	return L
n = int(input())
L = inp(n)
S = []
H = []
heapq.heapify(H)
for j in L:
	if j[0] == 'insert':
		heapq.heappush(H, j[1])
		S.append('insert' + ' ' + str(j[1]))
	elif j[0] == 'removeMin':
		if len(H) == 0:
			S.append('insert' + ' ' + str(0))
			S.append('removeMin')
		else:
			heapq.heappop(H)
			S.append('removeMin')
	else:
		k = j[1]
		if len(H) == 0:
			heapq.heappush(H, k)
			S.append('insert' + ' ' + str(k))
			S.append('getMin' + ' ' + str(k))
		elif k == H[0]:
			S.append('getMin' + ' ' + str(H[0]))
		elif k < H[0]:
			heapq.heappush(H, k)
			S.append('insert' + ' ' + str(k))
			S.append('getMin' + ' ' + str(k))
		else:
			while len(H) != 0 and k > H[0]:
				heapq.heappop(H)
				S.append('removeMin')
			if len(H) == 0 or H[0] != k:
				heapq.heappush(H, k)
				S.append('insert' + ' ' + str(k))
				S.append('getMin' + ' ' + str(k))
			else:
				S.append('getMin' + ' ' + str(H[0]))
print(str(len(S)))
for i in S:
	print(i)


import heapq
ot = []
n = int(input())
a = []
heapq.heapify(a)
for i in range(n):
	k1 = input()
	k = k1.split()
	if k[0] == 'insert':
		heapq.heappush(a, int(k[1]))
	elif k[0] == 'removeMin':
		if len(a) == 0:
			ot.append('insert 3')
		else:
			heapq.heappop(a)
	else:
		while len(a) != 0 and a[0] < int(k[1]):
			ot.append('removeMin')
			heapq.heappop(a)
		if len(a) == 0:
			ot.append('insert' + ' ' + k[1])
			heapq.heappush(a, int(k[1]))
		elif a[0] > int(k[1]):
			ot.append('insert' + ' ' + k[1])
			heapq.heappush(a, int(k[1]))
	ot.append(k1)
print(len(ot))
for x in ot:
	print(x)


import sys, bisect
from sys import stdin, stdout
from bisect import bisect_left, bisect_right, bisect, insort, insort_left, insort_right
from math import gcd, ceil, floor, sqrt
from collections import Counter, defaultdict, deque, OrderedDict
from queue import Queue, PriorityQueue
from string import ascii_lowercase
from heapq import *
from itertools import islice
sys.setrecursionlimit(10 ** 6)
INF = float('inf')
MOD = 998244353
mod = 10 ** 9 + 7

def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	for i in range(5, ceil(sqrt(n)) + 1, 6):
		if n % i == 0 or n % (i + 2) == 0:
			return False
	return True

def st():
	return list(stdin.readline().strip())

def inp():
	return int(stdin.readline())

def li():
	return list(map(int, stdin.readline().split()))

def mp():
	return map(int, stdin.readline().split())

def pr(n):
	stdout.write(str(n) + '\n')

def DFS(dictionary, vertex, visited):
	visited[vertex] = True
	stack = [vertex]
	print(vertex)
	while stack:
		a = stack.pop()
		for i in dictionary[a]:
			if not visited[i]:
				print(i)
				visited[i] = True
				stack.append(i)

def BFS(dictionary, vertex, visited):
	visited[vertex] = True
	q = deque()
	q.append(vertex)
	while q:
		a = q.popleft()
		for i in dictionary[a]:
			if not visited[i]:
				visited[i] = True
				q.append(i)
				print(i)

def soe(limit):
	l = [1] * (limit + 1)
	l[0] = 0
	l[1] = 0
	prime = []
	for i in range(2, limit + 1):
		if l[i]:
			for j in range(i * i, limit + 1, i):
				l[j] = 0
	for i in range(2, limit + 1):
		if l[i]:
			prime.append(i)
	return prime

def segsoe(low, high):
	limit = int(high ** 0.5) + 1
	prime = soe(limit)
	n = high - low + 1
	l = [0] * (n + 1)
	for i in range(len(prime)):
		lowlimit = low // prime[i] * prime[i]
		if lowlimit < low:
			lowlimit += prime[i]
		if lowlimit == prime[i]:
			lowlimit += prime[i]
		for j in range(lowlimit, high + 1, prime[i]):
			l[j - low] = 1
	for i in range(low, high + 1):
		if not l[i - low]:
			if i != 1:
				print(i)

def gcd(a, b):
	while b:
		a = a % b
		(b, a) = (a, b)
	return a

def power(a, n):
	r = 1
	while n:
		if n & 1:
			r = r * a
		a *= a
		n = n >> 1
	return r

def solve():
	n = inp()
	l = []
	ans = []
	for i in range(n):
		s = input().split()
		if s[0] == 'insert':
			a = int(s[1])
			heappush(l, a)
			ans.append(s[0] + ' ' + s[1])
		elif s[0] == 'getMin':
			a = int(s[1])
			if l:
				if a != l[0]:
					while l and l[0] < a:
						ans.append('removeMin')
						heappop(l)
					if not l:
						ans.append('insert ' + s[1])
						heappush(l, a)
					elif l[0] != a:
						ans.append('insert ' + s[1])
						heappush(l, a)
			else:
				ans.append('insert ' + s[1])
				heappush(l, a)
			ans.append(s[0] + ' ' + s[1])
		elif len(l) > 0:
			ans.append(s[0])
			heappop(l)
		else:
			ans.append('insert 100000000')
			ans.append(s[0])
	print(len(ans))
	for i in ans:
		print(i)
for _ in range(1):
	solve()


import heapq
a = []
h = []
heapq.heapify(h)
for _ in range(int(input())):
	l = input()
	if l.startswith('insert'):
		heapq.heappush(h, int(l.split()[1]))
	elif l.startswith('getMin'):
		m = int(l.split()[1])
		while len(h) > 0 and h[0] != m:
			if h[0] < m:
				heapq.heappop(h)
				a.append('removeMin')
			else:
				heapq.heappush(h, m)
				a.append('insert ' + str(m))
		if len(h) == 0:
			heapq.heappush(h, m)
			a.append('insert ' + str(m))
	elif l.startswith('removeMin'):
		if len(h) == 0:
			a.append('insert 1')
		else:
			heapq.heappop(h)
	a.append(l)
print(len(a))
print('\n'.join(a))


oplist = []
heap = []
sortd = True
for _ in range(int(input())):
	operation = input().strip()
	if operation.startswith('i'):
		heap.append(int(operation.split()[1]))
		oplist.append(operation)
		sortd = False
	elif operation.startswith('r'):
		if heap:
			if not sortd:
				heap.sort(reverse=True)
				sortd = True
			heap.pop()
		else:
			oplist.append('insert 1')
		oplist.append('removeMin')
	else:
		val = int(operation.split()[1])
		if not sortd:
			heap.sort(reverse=True)
			sortd = True
		while heap and heap[-1] < val:
			oplist.append('removeMin')
			heap.pop()
		if not heap or heap[-1] > val:
			oplist.append('insert {}'.format(val))
			heap.append(val)
		oplist.append(operation)
print(len(oplist))
print('\n'.join(oplist))