A binary heap is a Binary Tree with the following properties:
1) Its a complete tree (All levels are completely filled except possibly the last level and the last level has all keys as left as possible). This property of Binary Heap makes them suitable to be stored in an array.
2) A Binary Heap is either Min Heap or Max Heap. In a Min Binary Heap, the key at the root must be minimum among all keys present in Binary Heap. The same property must be recursively true for all nodes in Binary Tree. Max Binary Heap is similar to MinHeap.
You are given an empty Binary Min Heap and some queries and your task is to implement the three methods insertKey,  deleteKey,  and extractMin on the Binary Min Heap and call them as per the query given below:
1) 1  x  (a query of this type means to insert an element in the min-heap with value x )
2) 2  x  (a query of this type means to remove an element at position x from the min-heap)
3) 3  (a query like this removes the min element from the min-heap and prints it ).
Example 1:
Input:
Q = 7
Queries:
insertKey(4)
insertKey(2)
extractMin()
insertKey(6)
deleteKey(0)
extractMin()
extractMin()
Output: 2 6 - 1
Explanation: In the first test case for
query 
insertKey(4) the heap will have  {4}  
insertKey(2) the heap will be {2 4}
extractMin() removes min element from 
             heap ie 2 and prints it
             now heap is {4} 
insertKey(6) inserts 6 to heap now heap
             is {4 6}
deleteKey(0) delete element at position 0
             of the heap,now heap is {6}
extractMin() remove min element from heap
             ie 6 and prints it  now the
             heap is empty
extractMin() since the heap is empty thus
             no min element exist so -1
             is printed.
Example 2:
Input:
Q = 5
Queries:
insertKey(8)
insertKey(9)
deleteKey(1)
extractMin()
extractMin()
Output: 8 -1
Your Task:
You are required to complete the 3 methods insertKey() which take one argument the value to be inserted, deleteKey() which takes one argument the position from where the element is to be deleted and extractMin() which returns the minimum element in the heap(-1 if the heap is empty)
Expected Time Complexity: O(Q*Log(size of Heap) ).
Expected Auxiliary Space: O(1).
Constraints:
1 <= Q <= 10^{4}
1 <= x <= 10^{4}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Data structures

Starter code: #User function Template for python3



'''

heap = [0 for i in range(101)]  # our heap to be used

'''

#Function to insert a value in Heap.

def insertKey (x):

    global curr_size



#Function to delete a key at ith index.

def deleteKey (i):

    global curr_size



#Function to extract minimum value in heap and then to store 

#next minimum value at first index.

def extractMin ():



Solutions:
def heapify(heap, i):
	global curr_size
	left = 2 * i + 1
	right = 2 * i + 2
	if left < curr_size and heap[i] > heap[left]:
		mini = left
	else:
		mini = i
	if right < curr_size and heap[mini] > heap[right]:
		mini = right
	if i != mini:
		(heap[mini], heap[i]) = (heap[i], heap[mini])
		heapify(heap, mini)

def insertKey(x):
	global curr_size
	heap[curr_size] = x
	i = curr_size
	curr_size += 1
	parent = (i - 1) // 2
	while parent >= 0 and heap[parent] > heap[i]:
		(heap[i], heap[parent]) = (heap[parent], heap[i])
		i = parent
		parent = (parent - 1) // 2

def deleteKey(i):
	global curr_size
	if i >= curr_size or curr_size == 0:
		return -1
	heap[i] = float('-inf')
	parent = (i - 1) // 2
	while parent >= 0 and heap[parent] > heap[i]:
		(heap[i], heap[parent]) = (heap[parent], heap[i])
		i = parent
		parent = (parent - 1) // 2
	extractMin()

def extractMin():
	global curr_size
	if curr_size == 0:
		return -1
	mini = heap[0]
	heap[0] = heap[curr_size - 1]
	heap[curr_size - 1] = 0
	curr_size -= 1
	heapify(heap, 0)
	return mini


def left(i):
	return 2 * i + 1

def right(i):
	return 2 * i + 2

def parent(i):
	return (i - 1) // 2

def swap(i, j):
	global heap
	(heap[i], heap[j]) = (heap[j], heap[i])

def heapifyparent(i):
	while i > 0 and heap[i] < heap[parent(i)]:
		swap(i, parent(i))
		i = parent(i)

def heapify(i):
	small = i
	l = left(i)
	r = right(i)
	if l < curr_size and heap[small] > heap[l]:
		small = l
	if r < curr_size and heap[small] > heap[r]:
		small = r
	if small != i:
		swap(i, small)
		heapify(small)

def decreasekey(i, x):
	global heap, curr_size
	if i < curr_size and x < heap[i]:
		heap[i] = x
		heapifyparent(i)
		return True
	return False

def insertKey(x):
	global curr_size, heap
	if curr_size == 101:
		return False
	heap[curr_size] = x
	curr_size += 1
	heapifyparent(curr_size - 1)

def deleteKey(i):
	global curr_size
	if i < curr_size:
		decreasekey(i, -9223372036854775806)
		extractMin()
	else:
		return -1

def extractMin():
	global curr_size, heap
	if curr_size == 0:
		return -1
	if curr_size == 1:
		curr_size -= 1
		return heap[0]
	swap(0, curr_size - 1)
	curr_size -= 1
	heapify(0)
	return heap[curr_size]


def left(pos):
	return 2 * pos + 1

def right(pos):
	return 2 * pos + 2

def parent(pos):
	return (pos - 1) // 2

def swap(pos1, pos2):
	global heap
	(heap[pos1], heap[pos2]) = (heap[pos2], heap[pos1])

def isLeaf(pos):
	if left(pos) > curr_size - 1:
		return True
	return False

def heapifyT2B(pos):
	if not isLeaf(pos):
		smallest = pos
		if heap[smallest] > heap[left(pos)]:
			smallest = left(pos)
		if heap[smallest] > heap[right(pos)]:
			smallest = right(pos)
		if smallest != pos:
			swap(smallest, pos)
			heapifyT2B(smallest)

def heapifyB2T(pos):
	if pos > 0:
		if heap[pos] < heap[parent(pos)]:
			swap(pos, parent(pos))
			heapifyB2T(parent(pos))

def decreaseKey(pos, val):
	global heap
	if val > heap[pos]:
		return False
	heap[pos] = val
	heapifyB2T(pos)
	return True

def insertKey(x):
	global curr_size, heap
	if curr_size > 100:
		return False
	heap[curr_size] = x
	curr_size += 1
	heapifyB2T(curr_size - 1)

def deleteKey(i):
	global curr_size
	if i >= curr_size:
		return -1
	decreaseKey(i, -9223372036854775806)
	extractMin()

def extractMin():
	global heap, curr_size
	if curr_size == 0:
		return -1
	top_ele = heap[0]
	heap[0] = heap[curr_size - 1]
	curr_size -= 1
	heapifyT2B(0)
	return top_ele


def heapify(i):
	global curr_size, heap
	smallest = i
	(l, r) = (2 * i + 1, 2 * i + 2)
	if l < curr_size and heap[smallest] > heap[l]:
		smallest = l
	if r < curr_size and heap[smallest] > heap[r]:
		smallest = r
	if smallest != i:
		(heap[smallest], heap[i]) = (heap[i], heap[smallest])
		heapify(smallest)

def heapify2(i):
	global curr_size, heap
	parent = (i - 1) // 2
	while parent >= 0 and heap[parent] > heap[i]:
		(heap[parent], heap[i]) = (heap[i], heap[parent])
		(i, parent) = (parent, (parent - 1) // 2)

def insertKey(x):
	global curr_size, heap
	heap[curr_size] = x
	curr_size += 1
	heapify2(curr_size - 1)

def deleteKey(i):
	global heap, curr_size
	if i >= curr_size:
		return -1
	heap[i] = float('-inf')
	heapify2(i)
	extractMin()

def extractMin():
	global heap, curr_size
	if curr_size == 0:
		return -1
	(heap[0], heap[curr_size - 1]) = (heap[curr_size - 1], heap[0])
	r = heap[curr_size - 1]
	curr_size -= 1
	heapify(0)
	return r


def heapify_up(i):
	if i <= 0:
		return
	p_idx = (i - 1) // 2
	if heap[p_idx] > heap[i]:
		(heap[p_idx], heap[i]) = (heap[i], heap[p_idx])
		heapify_up(p_idx)

def heapify_down(i):
	global curr_size
	global heap
	(l_idx, r_idx) = (2 * i + 1, 2 * i + 2)
	(min_idx, smallest) = (i, heap[i])
	if l_idx < curr_size and smallest > heap[l_idx]:
		min_idx = l_idx
		smallest = heap[l_idx]
	if r_idx < curr_size and smallest > heap[r_idx]:
		min_idx = r_idx
		smallest = heap[r_idx]
	if min_idx != i:
		(heap[i], heap[min_idx]) = (heap[min_idx], heap[i])
		heapify_down(min_idx)

def insertKey(x):
	global curr_size
	global heap
	heap[curr_size] = x
	heapify_up(curr_size)
	curr_size += 1

def deleteKey(i):
	global heap
	global curr_size
	if i >= curr_size:
		return
	heap[i] = heap[curr_size - 1]
	curr_size -= 1
	if i < curr_size:
		heapify_down(i)
		heapify_up(i)

def extractMin():
	global curr_size
	global heap
	if curr_size > 0:
		min_value = heap[0]
		heap[0] = heap[curr_size - 1]
		curr_size -= 1
		heapify_down(0)
		return min_value
	return -1


def insertKey(x):
	global curr_size
	heap[curr_size] = x
	curr_size += 1
	i = curr_size - 1
	while i != 0 and heap[(i - 1) // 2] > heap[i]:
		(heap[(i - 1) // 2], heap[i]) = (heap[i], heap[(i - 1) // 2])
		i = (i - 1) // 2

def minheapify(arr, n, i):
	smallest = i
	l = 2 * i + 1
	r = 2 * i + 2
	if l < n and arr[l] < arr[smallest]:
		smallest = l
	if r < n and arr[r] < arr[smallest]:
		smallest = r
	if smallest != i:
		(arr[smallest], arr[i]) = (arr[i], arr[smallest])
		minheapify(arr, n, smallest)

def decreaseKey(i, val):
	if 0 <= i < curr_size:
		heap[i] = val
		while i != 0 and heap[i] < heap[(i - 1) // 2]:
			(heap[i], heap[(i - 1) // 2]) = (heap[(i - 1) // 2], heap[i])
			i = (i - 1) // 2

def deleteKey(i):
	global curr_size
	if 0 <= i < curr_size:
		if curr_size == 1:
			curr_size -= 1
			return
		decreaseKey(i, float('-inf'))
		extractMin()

def extractMin():
	global curr_size
	if curr_size == 0:
		return -1
	if curr_size == 1:
		curr_size -= 1
		return heap[0]
	(heap[curr_size - 1], heap[0]) = (heap[0], heap[curr_size - 1])
	item = heap[curr_size - 1]
	curr_size -= 1
	minheapify(heap, curr_size, 0)
	return item


def getParent(x):
	return (x - 1) // 2

def leftChild(x):
	return 2 * x + 1 if 2 * x + 1 < curr_size else -1

def rightChild(x):
	return 2 * x + 2 if 2 * x + 2 < curr_size else -1

def heapify():
	curr_ind = curr_size - 1
	while getParent(curr_ind) != -1 and heap[getParent(curr_ind)] > heap[curr_ind]:
		(heap[curr_ind], heap[getParent(curr_ind)]) = (heap[getParent(curr_ind)], heap[curr_ind])
		curr_ind = getParent(curr_ind)
	return

def heapifyDown(x):
	if x >= curr_size:
		return
	if getParent(x) != -1 and heap[x] < heap[getParent(x)]:
		(heap[x], heap[getParent(x)]) = (heap[getParent(x)], heap[x])
		heapifyDown(getParent(x))
	if leftChild(x) == -1 or (leftChild(x) != -1 and heap[x] < heap[leftChild(x)]):
		if rightChild(x) == -1 or (rightChild(x) != -1 and heap[x] < heap[rightChild(x)]):
			return
	if rightChild(x) == -1:
		(heap[x], heap[leftChild(x)]) = (heap[leftChild(x)], heap[x])
		heapifyDown(leftChild(x))
	elif leftChild(x) == -1:
		(heap[x], heap[rightChild(x)]) = (heap[rightChild(x)], heap[x])
		heapifyDown(rightChild(x))
	elif heap[rightChild(x)] < heap[leftChild(x)]:
		(heap[x], heap[rightChild(x)]) = (heap[rightChild(x)], heap[x])
		heapifyDown(rightChild(x))
	else:
		(heap[x], heap[leftChild(x)]) = (heap[leftChild(x)], heap[x])
		heapifyDown(leftChild(x))
	return

def insertKey(x):
	global curr_size
	heap[curr_size] = x
	curr_size += 1
	heapify()

def deleteKey(i):
	global curr_size
	if i >= curr_size:
		return
	heap[i] = heap[curr_size - 1]
	heap[curr_size - 1] = 0
	curr_size -= 1
	heapifyDown(i)

def extractMin():
	if curr_size == 0:
		return -1
	val = heap[0]
	deleteKey(0)
	return val


def heapify(i):
	global heap, curr_size
	target = i
	left = 2 * i + 1
	right = 2 * i + 2
	if left < curr_size and heap[left] < heap[target]:
		target = left
	if right < curr_size and heap[right] < heap[target]:
		target = right
	if target != i:
		(heap[i], heap[target]) = (heap[target], heap[i])
		heapify(target)

def heapify2(i):
	global heap
	parent = (i - 1) // 2
	while parent >= 0 and heap[parent] > heap[i]:
		(heap[parent], heap[i]) = (heap[i], heap[parent])
		(i, parent) = (parent, (parent - 1) // 2)

def insertKey(x):
	global heap, curr_size
	heap[curr_size] = x
	curr_size += 1
	heapify2(curr_size - 1)

def deleteKey(i):
	global heap, curr_size
	if i >= curr_size:
		return -1
	heap[i] = float('-inf')
	heapify2(i)
	extractMin()

def extractMin():
	global heap, curr_size
	if curr_size == 0:
		return -1
	(heap[0], heap[curr_size - 1]) = (heap[curr_size - 1], heap[0])
	r = heap[curr_size - 1]
	curr_size -= 1
	heapify(0)
	return r


def left(pos):
	return 2 * pos + 1

def right(pos):
	return 2 * pos + 2

def parent(pos):
	return (pos - 1) // 2

def isleaf(pos):
	if left(pos) > curr_size - 1:
		return True
	return False

def shiftdown(pos):
	if not isleaf(pos):
		smallest = pos
		if heap[smallest] > heap[left(pos)]:
			smallest = left(pos)
		if heap[smallest] > heap[right(pos)]:
			smallest = right(pos)
		if smallest != pos:
			(heap[pos], heap[smallest]) = (heap[smallest], heap[pos])
			shiftdown(smallest)

def shiftup(pos):
	if pos > 0:
		if heap[pos] < heap[parent(pos)]:
			(heap[pos], heap[parent(pos)]) = (heap[parent(pos)], heap[pos])
			shiftup(parent(pos))

def decreaseKey(pos, val):
	global heap
	if val > heap[pos]:
		return False
	heap[pos] = val
	shiftup(pos)
	return True

def insertKey(x):
	global curr_size, heap
	if curr_size > 100:
		return False
	heap[curr_size] = x
	curr_size += 1
	shiftup(curr_size - 1)

def deleteKey(i):
	global curr_size
	if i >= curr_size:
		return -1
	decreaseKey(i, float('-inf'))
	extractMin()

def extractMin():
	global curr_size, heap
	if curr_size == 0:
		return -1
	top = heap[0]
	heap[0] = heap[curr_size - 1]
	curr_size -= 1
	shiftdown(0)
	return top


def heapify(i):
	global curr_size, heap
	smallest = i
	while True:
		(l, r) = (2 * i + 1, 2 * i + 2)
		if l < curr_size and heap[smallest] > heap[l]:
			smallest = l
		if r < curr_size and heap[smallest] > heap[r]:
			smallest = r
		if smallest != i:
			(heap[smallest], heap[i]) = (heap[i], heap[smallest])
			i = smallest
		else:
			break

def insertKey(x):
	global curr_size, heap
	heap[curr_size] = x
	curr_size += 1
	i = curr_size - 1
	while i > 0:
		parent = (i - 1) // 2
		if heap[parent] > heap[i]:
			(heap[parent], heap[i]) = (heap[i], heap[parent])
			i = parent
		else:
			break

def deleteKey(i):
	global heap, curr_size
	if i >= curr_size:
		return -1
	heap[i] = float('-inf')
	while i > 0:
		parent = (i - 1) // 2
		if heap[parent] > heap[i]:
			(heap[parent], heap[i]) = (heap[i], heap[parent])
			i = parent
		else:
			break
	extractMin()

def extractMin():
	global heap, curr_size
	if curr_size == 0:
		return -1
	min_val = heap[0]
	heap[0] = heap[curr_size - 1]
	curr_size -= 1
	heapify(0)
	return min_val


import math

def insertKey(x):
	global curr_size
	heap[curr_size] = x
	curr_size += 1
	i = curr_size - 1
	while i > 0 and heap[(i - 1) // 2] > heap[i]:
		(heap[(i - 1) // 2], heap[i]) = (heap[i], heap[(i - 1) // 2])
		i = (i - 1) // 2

def deleteKey(i):
	global curr_size
	if i >= curr_size:
		return
	heap[i] = -math.inf
	while i > 0 and heap[(i - 1) // 2] > heap[i]:
		(heap[(i - 1) // 2], heap[i]) = (heap[i], heap[(i - 1) // 2])
		i = (i - 1) // 2
	extractMin()

def heapify(i):
	global curr_size
	if i >= curr_size:
		return
	left = 2 * i + 1
	right = 2 * i + 2
	smallest = i
	if left < curr_size and heap[smallest] > heap[left]:
		smallest = left
	if right < curr_size and heap[smallest] > heap[right]:
		smallest = right
	if i != smallest:
		(heap[i], heap[smallest]) = (heap[smallest], heap[i])
		heapify(smallest)

def extractMin():
	global curr_size
	if curr_size == 0:
		return -1
	res = heap[0]
	(heap[0], heap[curr_size - 1]) = (heap[curr_size - 1], heap[0])
	curr_size -= 1
	heapify(0)
	return res


def heapify(i):
	global curr_size, heap
	(lt, rt) = (2 * i + 1, 2 * i + 2)
	smallest = i
	if lt < curr_size and heap[lt] < heap[smallest]:
		smallest = lt
	if rt < curr_size and heap[rt] < heap[smallest]:
		smallest = rt
	if smallest != i:
		(heap[smallest], heap[i]) = (heap[i], heap[smallest])
		heapify(smallest)

def heapifyP(i):
	global curr_size, heap
	parent = (i - 1) // 2
	while parent >= 0 and heap[parent] > heap[i]:
		(heap[parent], heap[i]) = (heap[i], heap[parent])
		(i, parent) = (parent, (parent - 1) // 2)

def insertKey(x):
	global curr_size, heap
	heap[curr_size] = x
	curr_size += 1
	heapifyP(curr_size - 1)

def deleteKey(i):
	global curr_size, heap
	if i >= curr_size:
		return -1
	heap[i] = float('-inf')
	heapifyP(i)
	extractMin()

def extractMin():
	global heap, curr_size
	if curr_size == 0:
		return -1
	(heap[0], heap[curr_size - 1]) = (heap[curr_size - 1], heap[0])
	r = heap[curr_size - 1]
	curr_size -= 1
	heapify(0)
	return r


def parent(i):
	return (i - 1) // 2

def leftchild(i):
	return 2 * i + 1

def rightchild(i):
	return 2 * i + 2

def insertKey(x):
	global curr_size
	heap[curr_size] = x
	curr_size += 1
	i = curr_size - 1
	while i > 0 and heap[parent(i)] > heap[i]:
		p = parent(i)
		(heap[i], heap[p]) = (heap[p], heap[i])
		i = p

def decreasekey(index, value):
	global curr_size
	if index > curr_size:
		return
	heap[index] = value
	i = index
	while i != 0 and heap[parent(i)] > heap[i]:
		p = parent(i)
		(heap[i], heap[p]) = (heap[p], heap[i])
		i = p

def deleteKey(i):
	global curr_size
	if curr_size == 0:
		return
	if i >= curr_size:
		return
	decreasekey(i, -1)
	extractMin()
	return

def minifyheap(index):
	global curr_size
	if curr_size == 0:
		return
	lt = leftchild(index)
	rt = rightchild(index)
	smallest = index
	if lt < curr_size and heap[lt] < heap[smallest]:
		smallest = lt
	if rt < curr_size and heap[rt] < heap[smallest]:
		smallest = rt
	if smallest != index:
		(heap[smallest], heap[index]) = (heap[index], heap[smallest])
		minifyheap(smallest)

def extractMin():
	global curr_size
	if curr_size == 0:
		return -1
	output = heap[0]
	heap[0] = heap[curr_size - 1]
	heap[curr_size - 1] = 0
	curr_size -= 1
	minifyheap(0)
	return output


def heapify(ind):
	global curr_size
	par = ind
	if 2 * ind + 1 < curr_size and heap[2 * ind + 1] < heap[par]:
		par = 2 * ind + 1
	if 2 * ind + 2 < curr_size and heap[2 * ind + 2] < heap[par]:
		par = 2 * ind + 2
	if par != ind:
		(heap[par], heap[ind]) = (heap[ind], heap[par])
		heapify(par)
	return

def insertKey(x):
	global curr_size
	curr_size += 1
	heap[curr_size - 1] = x
	i = curr_size - 1
	while i > 0:
		if heap[(i - 1) // 2] <= heap[i]:
			break
		(heap[i], heap[(i - 1) // 2]) = (heap[(i - 1) // 2], heap[i])
		i = (i - 1) // 2

def deleteKey(i):
	global curr_size
	if i < curr_size:
		heap[i] = -999999999
		ind = i
		while ind > 0:
			if heap[(ind - 1) // 2] <= heap[ind]:
				break
			(heap[ind], heap[(ind - 1) // 2]) = (heap[(ind - 1) // 2], heap[ind])
			ind = (ind - 1) // 2
		extractMin()

def extractMin():
	global curr_size
	if curr_size == 0:
		return -1
	if curr_size == 1:
		curr_size -= 1
		return heap[curr_size]
	ans = heap[0]
	i = 0
	if i < curr_size:
		(heap[i], heap[curr_size - 1]) = (heap[curr_size - 1], heap[i])
		curr_size -= 1
		heapify(i)
	return ans


def insertKey(x):
	global curr_size
	if curr_size >= 101:
		return
	curr_size += 1
	decreaseKey(curr_size - 1, x)

def deleteKey(i):
	global curr_size
	if i >= curr_size:
		return
	decreaseKey(i, -float('inf'))
	extractMin()

def extractMin():
	global curr_size
	if curr_size == 0:
		return -1
	if curr_size == 1:
		curr_size -= 1
		return heap[0]
	ans = heap[0]
	heap[0] = heap[curr_size - 1]
	curr_size -= 1
	heapify(0)
	return ans

def decreaseKey(i, new):
	heap[i] = new
	while i != 0 and heap[parent(i)] > heap[i]:
		(heap[i], heap[parent(i)]) = (heap[parent(i)], heap[i])
		i = parent(i)

def heapify(i):
	global curr_size
	l = 2 * i + 1
	r = 2 * i + 2
	smallest = i
	if l < curr_size and heap[l] < heap[smallest]:
		smallest = l
	if r < curr_size and heap[r] < heap[smallest]:
		smallest = r
	if smallest != i:
		(heap[i], heap[smallest]) = (heap[smallest], heap[i])
		heapify(smallest)

def parent(i):
	return (i - 1) // 2


import math

def insertKey(x):
	global curr_size
	curr_size += 1
	heap[curr_size - 1] = x
	i = curr_size - 1
	while i >= 0 and heap[math.floor((i - 1) / 2)] > heap[i]:
		(heap[math.floor((i - 1) / 2)], heap[i]) = (heap[i], heap[math.floor((i - 1) / 2)])
		i = math.floor((i - 1) / 2)

def heapify(i):
	global curr_size
	lft = math.floor(i * 2 + 1)
	rgt = math.floor(i * 2 + 2)
	smallest = i
	if lft < curr_size and heap[smallest] > heap[lft]:
		smallest = lft
	if rgt < curr_size and heap[smallest] > heap[rgt]:
		smallest = rgt
	if smallest != i:
		(heap[smallest], heap[i]) = (heap[i], heap[smallest])
		heapify(smallest)

def deleteKey(i):
	global curr_size
	if curr_size == 0:
		return
	if i >= curr_size:
		return
	heap[i] = -1 * math.inf
	while i >= 0 and heap[math.floor((i - 1) / 2)] > heap[i]:
		(heap[math.floor((i - 1) / 2)], heap[i]) = (heap[i], heap[math.floor((i - 1) / 2)])
		i = math.floor((i - 1) / 2)
	extractMin()

def extractMin():
	global curr_size
	if curr_size == 0:
		return -1
	ret = heap[0]
	(heap[0], heap[curr_size - 1]) = (heap[curr_size - 1], heap[0])
	curr_size -= 1
	heapify(0)
	return ret


import math
heap = []

def parent(i):
	return (i - 1) // 2

def insertKey(x):
	global curr_size
	global heap
	if curr_size == 0:
		heap = []
	heap.append(x)
	curr_size += 1
	i = len(heap) - 1
	while i > 0 and heap[parent(i)] > heap[i]:
		(heap[i], heap[parent(i)]) = (heap[parent(i)], heap[i])
		i = parent(i)

def decrease_key(i, x):
	global heap
	heap[i] = x
	while i > 0 and heap[parent(i)] > heap[i]:
		(heap[i], heap[parent(i)]) = (heap[parent(i)], heap[i])
		i = parent(i)

def deleteKey(i):
	global curr_size
	global heap
	if curr_size == 0 or i > curr_size - 1:
		return
	decrease_key(i, -math.inf)
	extractMin()

def heapify(heap, i, n):
	smallest = i
	l = 2 * i + 1
	r = 2 * i + 2
	if l < n and heap[l] < heap[smallest]:
		smallest = l
	if r < n and heap[r] < heap[smallest]:
		smallest = r
	if i != smallest:
		(heap[smallest], heap[i]) = (heap[i], heap[smallest])
		heapify(heap, smallest, n)

def extractMin():
	global heap
	global curr_size
	if curr_size == 0:
		return -1
	res = heap[0]
	heap[0] = heap[-1]
	heap.pop()
	curr_size -= 1
	heapify(heap, 0, curr_size)
	return res


def siftUp(i):
	parent = (i - 1) // 2
	while i != 0 and heap[parent] > heap[i]:
		(heap[parent], heap[i]) = (heap[i], heap[parent])
		i = parent
		parent = (i - 1) // 2

def siftDown(i):
	left = i * 2 + 1
	right = i * 2 + 2
	while left < curr_size and heap[left] < heap[i] or (right < curr_size and heap[right] < heap[i]):
		smallest = left if right >= curr_size or heap[left] <= heap[right] else right
		(heap[smallest], heap[i]) = (heap[i], heap[smallest])
		i = smallest
		left = i * 2 + 1
		right = i * 2 + 2

def heapify():
	for i in range(curr_size - 1, -1, -1):
		siftDown(i)

def insertKey(x):
	global curr_size
	heap[curr_size] = x
	curr_size += 1
	siftUp(curr_size - 1)

def deleteKey(i):
	global curr_size
	if i >= curr_size:
		return
	(heap[i], heap[curr_size - 1]) = (heap[curr_size - 1], heap[i])
	heap[curr_size - 1] = 0
	curr_size -= 1
	heapify()

def extractMin():
	global curr_size
	if curr_size == 0:
		return -1
	minVal = heap[0]
	(heap[0], heap[curr_size - 1]) = (heap[curr_size - 1], heap[0])
	heap[curr_size - 1] = 0
	curr_size -= 1
	siftDown(0)
	return minVal


import math

def insertKey(x):
	global curr_size, heap
	heap[curr_size] = x
	curr_size += 1
	heapify2(curr_size - 1)

def heapify2(i):
	global curr_size, heap
	while i >= 0 and heap[(i - 1) // 2] > heap[i]:
		p = (i - 1) // 2
		(heap[p], heap[i]) = (heap[i], heap[p])
		i = p

def deleteKey(i):
	global curr_size, heap
	if i >= curr_size:
		return -1
	heap[i] = float('-inf')
	heapify2(i)
	extractMin()

def extractMin():
	global heap, curr_size
	if curr_size == 0:
		return -1
	res = heap[0]
	heap[0] = heap[curr_size - 1]
	heap.pop()
	curr_size -= 1
	minHeapify(0)
	return res

def minHeapify(i):
	global heap, current_size
	smallest = i
	n = curr_size
	lt = 2 * i + 1
	rt = 2 * i + 2
	if lt < n and heap[lt] < heap[smallest]:
		smallest = lt
	if rt < n and heap[rt] < heap[smallest]:
		smallest = rt
	if smallest != i:
		(heap[smallest], heap[i]) = (heap[i], heap[smallest])
		minHeapify(smallest)


import math

def heapify(arr, n, i):
	smallest = i
	l = 2 * i + 1
	r = 2 * i + 2
	if l < n and arr[l] < arr[smallest]:
		smallest = l
	if r < n and arr[r] < arr[smallest]:
		smallest = r
	if smallest != i:
		(arr[i], arr[smallest]) = (arr[smallest], arr[i])
		heapify(arr, n, smallest)

def insertKey(x):
	global curr_size
	heap[curr_size] = x
	curr_size += 1
	i = curr_size - 1
	parent = (i - 1) // 2
	while i > 0 and heap[parent] > heap[i]:
		(heap[parent], heap[i]) = (heap[i], heap[parent])
		i = (i - 1) // 2
		parent = (i - 1) // 2

def decreaseKey(i, new_val):
	heap[i] = new_val
	parent = (i - 1) // 2
	while i > 0 and heap[(i - 1) // 2] > heap[i]:
		(heap[parent], heap[i]) = (heap[i], heap[parent])
		i = (i - 1) // 2
		parent = (i - 1) // 2

def deleteKey(i):
	global curr_size
	if i < curr_size:
		decreaseKey(i, float('-inf'))
		extractMin()

def extractMin():
	global curr_size
	if curr_size <= 0:
		return -1
	res = heap[0]
	heap[0] = heap[curr_size - 1]
	curr_size -= 1
	heapify(heap, curr_size, 0)
	return res


from heapq import heappush, heappop, heapify

def heapify(i):
	global curr_size, heap
	smallest = i
	(l, r) = (2 * i + 1, 2 * i + 2)
	if l < curr_size and heap[smallest] > heap[l]:
		smallest = l
	if r < curr_size and heap[smallest] > heap[r]:
		smallest = r
	if smallest != i:
		(heap[smallest], heap[i]) = (heap[i], heap[smallest])
		heapify(smallest)

def heapify2(i):
	global curr_size, heap
	parent = (i - 1) // 2
	while parent >= 0 and heap[parent] > heap[i]:
		(heap[parent], heap[i]) = (heap[i], heap[parent])
		(i, parent) = (parent, (parent - 1) // 2)

def insertKey(x):
	global curr_size, heap
	heap[curr_size] = x
	curr_size += 1
	heapify2(curr_size - 1)

def deleteKey(i):
	global heap, curr_size
	if i >= curr_size:
		return -1
	heap[i] = float('-inf')
	heapify2(i)
	extractMin()

def extractMin():
	global heap, curr_size
	if curr_size == 0:
		return -1
	(heap[0], heap[curr_size - 1]) = (heap[curr_size - 1], heap[0])
	r = heap[curr_size - 1]
	curr_size -= 1
	heapify(0)
	return r


def insertKey(x):
	global curr_size
	heap[curr_size] = x
	curr_size += 1
	indx = curr_size - 1
	while indx > 0 and heap[(indx - 1) // 2] > heap[indx]:
		(heap[(indx - 1) // 2], heap[indx]) = (heap[indx], heap[(indx - 1) // 2])
		indx = (indx - 1) // 2

def deleteKey(i):
	global curr_size
	if curr_size <= i:
		return
	heap[i] = float('-inf')
	indx = i
	while indx > 0 and heap[(indx - 1) // 2] > heap[indx]:
		(heap[(indx - 1) // 2], heap[indx]) = (heap[indx], heap[(indx - 1) // 2])
		indx = (indx - 1) // 2
	extractMin()

def extractMin():
	global curr_size
	if curr_size == 0:
		return -1
	(heap[0], heap[curr_size - 1]) = (heap[curr_size - 1], heap[0])
	ext = heap.pop(curr_size - 1)
	curr_size -= 1
	heapify(0)
	return ext

def heapify(indx):
	global curr_size
	left_indx = 2 * indx + 1
	right_indx = 2 * indx + 2
	smallest = indx
	if left_indx < curr_size and heap[left_indx] < heap[indx]:
		smallest = left_indx
	if right_indx < curr_size and heap[smallest] > heap[right_indx]:
		smallest = right_indx
	if smallest != indx:
		(heap[indx], heap[smallest]) = (heap[smallest], heap[indx])
		heapify(smallest)


import math

def insertKey(x):
	global curr_size
	heap.append(x)
	curr_size += 1
	i = curr_size - 1
	p = get_parent(i)
	while i > 0 and heap[p] > heap[i]:
		(heap[p], heap[i]) = (heap[i], heap[p])
		i = p
		p = get_parent(i)
	return heap

def getParent(x):
	return (x - 1) // 2

def leftChild(x):
	return 2 * x + 1 if 2 * x + 1 < curr_size else -1

def rightChild(x):
	return 2 * x + 2 if 2 * x + 2 < curr_size else -1

def heapify():
	curr_ind = curr_size - 1
	while getParent(curr_ind) != -1 and heap[getParent(curr_ind)] > heap[curr_ind]:
		(heap[curr_ind], heap[getParent(curr_ind)]) = (heap[getParent(curr_ind)], heap[curr_ind])
		curr_ind = getParent(curr_ind)
	return

def heapifyDown(x):
	if x >= curr_size:
		return
	if getParent(x) != -1 and heap[x] < heap[getParent(x)]:
		(heap[x], heap[getParent(x)]) = (heap[getParent(x)], heap[x])
		heapifyDown(getParent(x))
	if leftChild(x) == -1 or (leftChild(x) != -1 and heap[x] < heap[leftChild(x)]):
		if rightChild(x) == -1 or (rightChild(x) != -1 and heap[x] < heap[rightChild(x)]):
			return
	if rightChild(x) == -1:
		(heap[x], heap[leftChild(x)]) = (heap[leftChild(x)], heap[x])
		heapifyDown(leftChild(x))
	elif leftChild(x) == -1:
		(heap[x], heap[rightChild(x)]) = (heap[rightChild(x)], heap[x])
		heapifyDown(rightChild(x))
	elif heap[rightChild(x)] < heap[leftChild(x)]:
		(heap[x], heap[rightChild(x)]) = (heap[rightChild(x)], heap[x])
		heapifyDown(rightChild(x))
	else:
		(heap[x], heap[leftChild(x)]) = (heap[leftChild(x)], heap[x])
		heapifyDown(leftChild(x))
	return

def insertKey(x):
	global curr_size
	heap[curr_size] = x
	curr_size += 1
	heapify()

def deleteKey(i):
	global curr_size
	if i >= curr_size:
		return
	heap[i] = heap[curr_size - 1]
	heap[curr_size - 1] = 0
	curr_size -= 1
	heapifyDown(i)

def extractMin():
	if curr_size == 0:
		return -1
	val = heap[0]
	deleteKey(0)
	return val


def swim(i):
	if i == 0:
		return
	parent_ind = (i - 1) // 2
	if heap[i] < heap[parent_ind]:
		(heap[i], heap[parent_ind]) = (heap[parent_ind], heap[i])
		swim(parent_ind)

def sink(i):
	global curr_size
	if i > curr_size:
		return
	(lc_ind, rc_ind) = (2 * i + 1, 2 * i + 2)
	lc_val = rc_val = float('inf')
	if lc_ind < curr_size:
		lc_val = heap[lc_ind]
		if rc_ind < curr_size:
			rc_val = heap[rc_ind]
	if heap[i] > min(lc_val, rc_val):
		if lc_val <= rc_val:
			(heap[i], heap[lc_ind]) = (heap[lc_ind], heap[i])
			sink(lc_ind)
		else:
			(heap[i], heap[rc_ind]) = (heap[rc_ind], heap[i])
			sink(rc_ind)

def insertKey(x):
	global curr_size
	heap[curr_size] = x
	curr_size += 1
	swim(curr_size - 1)

def deleteKey(i):
	global curr_size
	if i >= curr_size:
		return
	curr_size -= 1
	heap[i] = heap[curr_size]
	sink(i)
	swim(i)

def extractMin():
	global curr_size
	if curr_size == 0:
		return -1
	ret = heap[0]
	curr_size -= 1
	heap[0] = heap[curr_size]
	sink(0)
	return ret


def minHeapify(i):
	global curr_size, heap
	m = i
	l = 2 * i + 1
	r = l + 1
	if l < curr_size and heap[l] < heap[m]:
		m = l
	if r < curr_size and heap[r] < heap[m]:
		m = r
	if i != m:
		t = heap[i]
		heap[i] = heap[m]
		heap[m] = t
		minHeapify(m)

def insertKey(x):
	global curr_size, heap
	if curr_size == 0:
		heap[0] = x
		curr_size = 1
		return
	heap[curr_size] = x
	curr_size += 1
	c = curr_size - 1
	while c > 0:
		p = int((c - 1) / 2)
		if heap[p] > heap[c]:
			t = heap[p]
			heap[p] = heap[c]
			heap[c] = t
			c = p
		else:
			break

def deleteKey(i):
	global curr_size, heap
	if i >= curr_size:
		return -1
	if curr_size < 2:
		curr_size = 0
		return
	if i == curr_size - 1:
		curr_size -= 1
		return
	c = i
	heap[i] = -999999
	while c > 0:
		p = int((c - 1) / 2)
		if heap[p] > heap[c]:
			t = heap[p]
			heap[p] = heap[c]
			heap[c] = t
			c = p
		else:
			break
	extractMin()

def extractMin():
	global curr_size, heap
	if curr_size == 0:
		return -1
	if curr_size == 1:
		curr_size = 0
		return heap[0]
	temp = heap[0]
	heap[0] = heap[curr_size - 1]
	curr_size -= 1
	minHeapify(0)
	return temp


def heapify(i):
	global curr_size, heap
	smallest = i
	(l, r) = (2 * i + 1, 2 * i + 2)
	if l < curr_size and heap[l] < heap[smallest]:
		smallest = l
	if r < curr_size and heap[r] < heap[smallest]:
		smallest = r
	if smallest != i:
		(heap[i], heap[smallest]) = (heap[smallest], heap[i])
		heapify(smallest)

def decKey(i):
	global curr_size, heap
	parent = (i - 1) // 2
	while parent >= 0 and heap[parent] > heap[i]:
		(heap[parent], heap[i]) = (heap[i], heap[parent])
		(i, parent) = (parent, (parent - 1) // 2)

def insertKey(x):
	global curr_size, heap
	if curr_size == len(heap):
		return
	curr_size += 1
	heap[curr_size - 1] = x
	decKey(curr_size - 1)

def deleteKey(i):
	global curr_size, heap
	if i >= curr_size:
		return -1
	heap[i] = -999999
	decKey(i)
	extractMin()

def extractMin():
	global curr_size, heap
	if curr_size == 0:
		return -1
	temp = heap[0]
	heap[0] = heap[curr_size - 1]
	curr_size -= 1
	heapify(0)
	return temp


def heapify(i):
	p = (i - 1) // 2
	while p >= 0:
		if heap[p] > heap[i]:
			(heap[p], heap[i]) = (heap[i], heap[p])
		i = p
		p = (p - 1) // 2

def insertKey(x):
	global curr_size
	heap[curr_size] = x
	heapify(curr_size)
	curr_size = curr_size + 1

def heapify2(i):
	global curr_size
	l = i * 2 + 1
	r = i * 2 + 2
	k = i
	if l < curr_size and heap[l] < heap[i]:
		i = l
	if r < curr_size and heap[r] < heap[i]:
		i = r
	if i != k:
		(heap[i], heap[k]) = (heap[k], heap[i])
		heapify2(i)

def deleteKey(i):
	global curr_size
	if i >= curr_size:
		return -1
	heap[i] = float('-inf')
	heapify(i)
	heap[0] = heap[curr_size - 1]
	heap[curr_size - 1] = 0
	curr_size = curr_size - 1
	heapify2(0)

def extractMin():
	global curr_size
	if curr_size == 0:
		return -1
	pos = heap[0]
	heap[0] = heap[curr_size - 1]
	heap[curr_size - 1] = 0
	curr_size = curr_size - 1
	heapify2(0)
	return pos


import math

def insertKey(x):
	global curr_size
	global heap
	heap[curr_size] = x
	curr_size += 1
	i = curr_size - 1
	while i > 0 and heap[(i - 1) // 2] > heap[i]:
		(heap[(i - 1) // 2], heap[i]) = (heap[i], heap[(i - 1) // 2])
		i = (i - 1) // 2

def deleteKey(i):
	global curr_size
	if i >= curr_size:
		return
	heap[i] = -math.inf
	while i > 0 and heap[(i - 1) // 2] > heap[i]:
		(heap[(i - 1) // 2], heap[i]) = (heap[i], heap[(i - 1) // 2])
		i = (i - 1) // 2
	extractMin()

def heapify(i):
	global curr_size
	le = 2 * i + 1
	re = 2 * i + 2
	smallest = i
	if le < curr_size and heap[le] < heap[smallest]:
		smallest = le
	if re < curr_size and heap[re] < heap[smallest]:
		smallest = re
	if smallest != i:
		(heap[smallest], heap[i]) = (heap[i], heap[smallest])
		heapify(smallest)
	return

def extractMin():
	global curr_size
	if curr_size == 0:
		return -1
	res = heap[0]
	heap[0] = heap[curr_size - 1]
	heap.pop(curr_size - 1)
	curr_size -= 1
	heapify(0)
	return res


def heapify2(i):
	global heap
	p = (i - 1) // 2
	while p >= 0 and heap[p] > heap[i]:
		(heap[p], heap[i]) = (heap[i], heap[p])
		(i, p) = (p, (p - 1) // 2)

def insertKey(x):
	global curr_size, heap
	heap[curr_size] = x
	curr_size += 1
	heapify2(curr_size - 1)

def deleteKey(i):
	global curr_size, heap
	n = curr_size
	if n == 0 or i >= n:
		return -1
	else:
		heap[i] = -99999
		heapify2(i)
		extractMin()

def extractMin():
	global heap, curr_size
	if curr_size == 0:
		return -1
	res = heap[0]
	heap[0] = heap[curr_size - 1]
	curr_size -= 1
	heapify(0)
	return res

def heapify(i):
	global heap, curr_size
	(lc, rc) = (2 * i + 1, 2 * i + 2)
	smallest = i
	if lc < curr_size and heap[smallest] > heap[lc]:
		smallest = lc
	if rc < curr_size and heap[smallest] > heap[rc]:
		smallest = rc
	if smallest != i:
		(heap[i], heap[smallest]) = (heap[smallest], heap[i])
		heapify(smallest)


def left(pos):
	return 2 * pos + 1

def right(pos):
	return 2 * pos + 2

def parent(pos):
	return (pos - 1) // 2

def swap(pos1, pos2):
	global heap
	(heap[pos1], heap[pos2]) = (heap[pos2], heap[pos1])

def isLeaf(pos):
	if left(pos) > curr_size - 1:
		return True
	return False

def heapify(i):
	global curr_size, heap
	smallest = i
	(l, r) = (2 * i + 1, 2 * i + 2)
	if l < curr_size and heap[smallest] > heap[l]:
		smallest = l
	if r < curr_size and heap[smallest] > heap[r]:
		smallest = r
	if smallest != i:
		(heap[smallest], heap[i]) = (heap[i], heap[smallest])
		heapify(smallest)

def heapify2(i):
	global curr_size, heap
	parent = (i - 1) // 2
	while parent >= 0 and heap[parent] > heap[i]:
		(heap[parent], heap[i]) = (heap[i], heap[parent])
		(i, parent) = (parent, (parent - 1) // 2)

def decreaseKey(pos, val):
	global heap
	if val > heap[pos]:
		return False
	heap[pos] = val
	heapify2(pos)
	return True

def insertKey(x):
	global curr_size, heap
	if curr_size > 100:
		return False
	heap[curr_size] = x
	curr_size += 1
	heapify2(curr_size - 1)

def deleteKey(i):
	global heap, curr_size
	if i >= curr_size:
		return -1
	heap[i] = float('-inf')
	heapify2(i)
	extractMin()

def extractMin():
	global heap, curr_size
	if curr_size == 0:
		return -1
	top_ele = heap[0]
	heap[0] = heap[curr_size - 1]
	curr_size -= 1
	heapify(0)
	return top_ele


def left(pos):
	return 2 * pos + 1

def right(pos):
	return 2 * pos + 2

def parent(pos):
	return (pos - 1) // 2

def swap(pos1, pos2):
	global heap
	(heap[pos1], heap[pos2]) = (heap[pos2], heap[pos1])

def isLeaf(pos):
	if left(pos) > curr_size - 1:
		return True
	return False

def heapify(i):
	global curr_size, heap
	smallest = i
	(l, r) = (2 * i + 1, 2 * i + 2)
	if l < curr_size and heap[smallest] > heap[l]:
		smallest = l
	if r < curr_size and heap[smallest] > heap[r]:
		smallest = r
	if smallest != i:
		(heap[smallest], heap[i]) = (heap[i], heap[smallest])
		heapify(smallest)

def heapifyB2T(pos):
	if pos > 0:
		if heap[pos] < heap[parent(pos)]:
			swap(pos, parent(pos))
			heapifyB2T(parent(pos))

def decreaseKey(pos, val):
	global heap
	if val > heap[pos]:
		return False
	heap[pos] = val
	heapifyB2T(pos)
	return True

def insertKey(x):
	global curr_size, heap
	if curr_size > 100:
		return False
	heap[curr_size] = x
	curr_size += 1
	heapifyB2T(curr_size - 1)

def deleteKey(i):
	global curr_size
	if i >= curr_size:
		return -1
	decreaseKey(i, -9223372036854775806)
	extractMin()

def extractMin():
	global heap, curr_size
	if curr_size == 0:
		return -1
	top_ele = heap[0]
	heap[0] = heap[curr_size - 1]
	curr_size -= 1
	heapify(0)
	return top_ele