There are given N ropes of different lengths, we need to connect these ropes into one rope. The cost to connect two ropes is equal to sum of their lengths. The task is to connect the ropes with minimum cost. Given N size array arr[] contains the lengths of the ropes. 
Example 1:
Input:
n = 4
arr[] = {4, 3, 2, 6}
Output: 
29
Explanation:
We can connect the ropes in following ways.
1) First connect ropes of lengths 2 and 3.
Which makes the array {4, 5, 6}. Cost of
this operation 2+3 = 5. 
2) Now connect ropes of lengths 4 and 5.
Which makes the array {9, 6}. Cost of
this operation 4+5 = 9.
3) Finally connect the two ropes and all
ropes have connected. Cost of this 
operation 9+6 =15
Total cost for connecting all ropes is 5
+ 9 + 15 = 29. This is the optimized cost
for connecting ropes. 
Other ways of connecting ropes would always 
have same or more cost. For example, if we 
connect 4 and 6 first (we get three rope of 3,
2 and 10), then connect 10 and 3 (we get
two rope of 13 and 2). Finally we
connect 13 and 2. Total cost in this way
is 10 + 13 + 15 = 38.
Example 2:
Input:
n = 5
arr[] = {4, 2, 7, 6, 9}
Output: 
62 
Explanation:
First, connect ropes 4 and 2, which makes
the array {6,7,6,9}. Cost of
this operation 4+2 = 6. Next, add ropes 
6 and 6, which results in {12,7,9}. 
Cost of this operation 6+6 = 12.
Then, add 7 and 9, which makes the array {12,16}. 
Cost of this operation 7+9 = 16. And
finally, add these two which gives {28}.
Hence, the total cost is 6 + 12 + 16 + 
28 = 62.
Your Task:
You don't need to read input or print anything. Your task isto complete the function minCost() which takes an integer array arr[] and an integer n as arguments and returns the minimum cost.
Expected Time Complexity : O(nlogn)
Expected Auxilliary Space : O(n)
Constraints:
1 ≤ N ≤ 200000
1 ≤ arr[i] ≤ 10^{6}

Source: geeksforgeeks | Difficulty: EASY
Tags: Data structures

Starter code: #User function Template for python3



class Solution:

    #Function to return the minimum cost of connecting the ropes.

    def minCost(self,arr,n) :

    

        # code here

Solutions:
from heapq import *

class Solution:

	def minCost(self, arr, n):
		heap = []
		for elm in arr:
			heappush(heap, elm)
		ans = 0
		while len(heap) > 1:
			a = heappop(heap)
			b = heappop(heap)
			ans += a + b
			heappush(heap, a + b)
		return ans


from heapq import *

class Solution:

	def minCost(self, heap, n):
		heapify(heap)
		ans = 0
		for i in range(n - 1):
			a = heappop(heap)
			b = heappop(heap)
			ans += a + b
			heappush(heap, a + b)
		return ans


from heapq import *

class Solution:

	def minCost(self, heap, n):
		heapify(heap)
		ans = 0
		while len(heap) != 1:
			a = heappop(heap)
			b = heappop(heap)
			ans += a + b
			heappush(heap, a + b)
		return ans


import heapq

class Solution:

	def minCost(self, arr, n):
		res = 0
		minheap = []
		for i in range(n):
			heapq.heappush(minheap, arr[i])
		while len(minheap) > 1:
			p1 = heapq.heappop(minheap)
			p2 = heapq.heappop(minheap)
			cost = p1 + p2
			res = res + cost
			heapq.heappush(minheap, cost)
		return res


import heapq

class Solution:

	def minCost(self, arr, n):
		heapq.heapify(arr)
		ans = 0
		while len(arr) > 1:
			t1 = heapq.heappop(arr)
			t2 = heapq.heappop(arr)
			t1 = t1 + t2
			ans += t1
			heapq.heappush(arr, t1)
		return ans


import heapq

class Solution:

	def minCost(self, arr, n):
		heapq.heapify(arr)
		ans = 0
		while n > 1:
			a = heapq.heappop(arr)
			b = heapq.heappop(arr)
			s = a + b
			ans += s
			heapq.heappush(arr, s)
			n -= 1
		return ans


import heapq as hq

class Solution:

	def minCost(self, arr, n):
		heap = []
		ans = []
		for i in arr:
			hq.heappush(heap, i)
		su = 0
		while len(heap) > 1:
			su = hq.heappop(heap) + hq.heappop(heap)
			ans.append(su)
			hq.heappush(heap, su)
		return sum(ans)


from queue import PriorityQueue

class Solution:

	def minCost(self, a, n):
		min_heap = []
		for num in a:
			heapq.heappush(min_heap, num)
		total_cost = 0
		while len(min_heap) > 1:
			val_1 = heapq.heappop(min_heap)
			val_2 = heapq.heappop(min_heap)
			val = val_1 + val_2
			total_cost += val
			heapq.heappush(min_heap, val)
		return total_cost


import heapq

class Solution:

	def minCost(self, arr, n):
		min_heap = []
		for i in range(n):
			heapq.heappush(min_heap, arr[i])
		cost = 0
		while n > 1:
			first = heapq.heappop(min_heap)
			second = heapq.heappop(min_heap)
			heapq.heappush(min_heap, first + second)
			n -= 1
			cost += first + second
		return cost


class Solution:

	def minCost(self, arr, n):
		import heapq
		heapq.heapify(arr)
		res = 0
		while len(arr) >= 2:
			new = heapq.heappop(arr) + heapq.heappop(arr)
			res += new
			heapq.heappush(arr, new)
		return res


class Solution:

	def minCost(self, arr, n):
		import heapq
		heapq.heapify(arr)
		sum_curr = 0
		while len(arr) > 1:
			e1 = heapq.heappop(arr)
			if len(arr) != 0:
				e2 = heapq.heappop(arr)
			sum = e1 + e2
			sum_curr = sum_curr + e1 + e2
			heapq.heappush(arr, sum)
		return sum_curr


class Solution:

	def minCost(self, arr, n):
		import heapq
		heapq.heapify(arr)
		res = 0
		while len(arr) > 1:
			first = heapq.heappop(arr)
			second = heapq.heappop(arr)
			res += first + second
			heapq.heappush(arr, first + second)
		return res


import heapq

class Solution:

	def minCost(self, arr, n):
		pq = []
		for i in range(n):
			heapq.heappush(pq, arr[i])
		cost = 0
		while len(pq) > 1:
			first = heapq.heappop(pq)
			second = heapq.heappop(pq)
			mergelen = first + second
			cost += mergelen
			heapq.heappush(pq, mergelen)
		return cost


import heapq

class Solution:

	def minCost(self, arr, n):
		heapq.heapify(arr)
		z = 0
		for i in range(n - 1):
			x = heapq.heappop(arr)
			y = heapq.heappop(arr)
			z += x + y
			heapq.heappush(arr, x + y)
		return z


class Solution:

	def minCost(self, arr, n):
		import heapq
		heapq.heapify(arr)
		list1 = []
		while len(arr) > 1:
			first = heapq.heappop(arr)
			second = heapq.heappop(arr)
			arr.append(first + second)
			list1.append(first + second)
		return sum(list1)


import heapq as hq

class Solution:

	def minCost(self, arr, n):
		heap = []
		for i in arr:
			hq.heappush(heap, i)
		count = 0
		while len(heap) > 1:
			num1 = hq.heappop(heap)
			num2 = hq.heappop(heap)
			tmp = num1 + num2
			count += tmp
			hq.heappush(heap, tmp)
		return count


class Solution:
	import heapq

	def minCost(self, arr, n):
		heap = []
		cost = 0
		for x in arr:
			heapq.heappush(heap, x)
		while len(heap) > 1:
			a = heap[0]
			heapq.heappop(heap)
			b = heap[0]
			heapq.heappop(heap)
			s = a + b
			cost += s
			heapq.heappush(heap, s)
		return cost


import heapq

class Solution:

	def minCost(self, arr, n):
		arr.sort()
		cost = 0
		heap = []
		for i in arr:
			heapq.heappush(heap, i)
		while len(heap) > 1:
			first = heapq.heappop(heap)
			second = heapq.heappop(heap)
			heapq.heappush(heap, first + second)
			cost = cost + first + second
		return cost


from heapq import heappush, heappop, heapify

class Solution:

	def minCost(self, a, n):
		heapify(a)
		s = 0
		while len(a) != 1:
			x = heappop(a) + heappop(a)
			s += x
			heappush(a, x)
		return s


import heapq

class Solution:

	def minCost(self, arr, n):
		minheap = []
		curr_sum = 0
		total_sum = 0
		for i in range(0, len(arr)):
			heapq.heappush(minheap, arr[i])
		while len(minheap) >= 2:
			temp1 = heapq.heappop(minheap)
			temp2 = heapq.heappop(minheap)
			curr_sum = temp1 + temp2
			total_sum = total_sum + curr_sum
			if minheap:
				heapq.heappush(minheap, curr_sum)
		return total_sum


import heapq

class Solution:

	def minCost(self, arr, n):
		minheap = []
		summ = 0
		stack = []
		for i in range(0, len(arr)):
			heapq.heappush(minheap, arr[i])
		while len(minheap) >= 2:
			temp1 = heapq.heappop(minheap)
			temp2 = heapq.heappop(minheap)
			summ = temp1 + temp2
			stack.append(summ)
			if minheap:
				heapq.heappush(minheap, summ)
		return sum(stack)


import heapq

class Solution:

	def minCost(self, arr, n):
		sum = 0
		ans = 0
		heapq.heapify(arr)
		for i in range(n - 1):
			first = heapq.heappop(arr)
			second = heapq.heappop(arr)
			sum = first + second
			ans += sum
			heapq.heappush(arr, sum)
		return ans


import heapq

class Solution:

	def minCost(self, arr, n):
		min_cost = 0
		heapq.heapify(arr)
		k = 0
		while len(arr) > 1:
			p1 = heapq.heappop(arr)
			p2 = heapq.heappop(arr)
			p = p1 + p2
			min_cost += p
			heapq.heappush(arr, p)
		return min_cost


import heapq

class Solution:

	def minCost(self, arr, n):
		heap = []
		for i in range(n):
			heapq.heappush(heap, arr[i])
		totalCost = 0
		while len(heap) >= 2:
			first = heapq.heappop(heap)
			second = heapq.heappop(heap)
			totalCost += first + second
			heapq.heappush(heap, first + second)
		return totalCost


from heapq import *

class Solution:

	def minCost(self, arr, n):
		heap = []
		for i in arr:
			heappush(heap, i)
		res = 0
		for i in range(1, n):
			first = heappop(heap)
			second = heappop(heap)
			res += first + second
			heappush(heap, first + second)
		return res


import heapq

class Solution:

	def minCost(self, rope, n):
		heap = rope
		heapq.heapify(heap)
		cost = 0
		while len(heap) > 1:
			x = heapq.heappop(heap)
			y = heapq.heappop(heap)
			cost += x + y
			heapq.heappush(heap, x + y)
		return cost


import heapq

class Solution:

	def minCost(self, arr, n):
		minheap = []
		cost = 0
		for i in range(0, n):
			heapq.heappush(minheap, arr[i])
		while len(minheap) > 1:
			ele1 = heapq.heappop(minheap)
			ele2 = heapq.heappop(minheap)
			total = ele1 + ele2
			cost += total
			heapq.heappush(minheap, total)
		return cost


import heapq

class Solution:

	def minCost(self, arr, n):
		heap = arr.copy()
		heapq.heapify(heap)
		s = 0
		while len(heap) != 1:
			m1 = heapq.heappop(heap)
			m2 = heapq.heappop(heap)
			s += m1 + m2
			heapq.heappush(heap, m1 + m2)
		return s


import heapq

class Solution:

	def minCost(self, arr, n):
		if n == 0 or n == 1:
			return 0
		heapq.heapify(arr)
		cost = 0
		for i in range(n - 1):
			r1 = heapq.heappop(arr)
			r2 = heapq.heappop(arr)
			sum_of_2ropes = r1 + r2
			cost = cost + sum_of_2ropes
			heapq.heappush(arr, sum_of_2ropes)
		return cost


class Solution:

	def minCost(self, arr, n):
		import heapq
		heapq.heapify(arr)
		tot = 0
		while True:
			try:
				pop_val_1 = heapq.heappop(arr)
				pop_val_2 = heapq.heappop(arr)
				push_val = pop_val_1 + pop_val_2
				tot += push_val
				heapq.heappush(arr, push_val)
			except:
				break
		return tot


import heapq as hq

class Solution:

	def minCost(self, arr, n):
		heap = []
		for i in range(len(arr)):
			hq.heappush(heap, arr[i])
		res = []
		count = 0
		while len(heap) > 1:
			temp1 = hq.heappop(heap)
			temp2 = hq.heappop(heap)
			count += temp1 + temp2
			hq.heappush(heap, temp1 + temp2)
		return count


import heapq

class Solution:

	def minCost(self, arr, n):
		heapq.heapify(arr)
		res = 0
		while len(arr) > 1:
			f = heapq.heappop(arr)
			s = heapq.heappop(arr)
			res += f + s
			heapq.heappush(arr, f + s)
		return res


import heapq

class Solution:

	def minCost(self, arr, n):
		heapq.heapify(arr)
		cost = 0
		while len(arr) >= 2:
			first = heapq.heappop(arr)
			second = heapq.heappop(arr)
			cost += first + second
			heapq.heappush(arr, first + second)
		return cost


class Solution:

	def minCost(self, arr, n):
		sum = 0
		cost = 0
		minHeap = []
		for i in range(n):
			heapq.heappush(minHeap, arr[i])
		while len(minHeap) >= 2:
			sum = 0
			a = heapq.heappop(minHeap)
			b = heapq.heappop(minHeap)
			sum = a + b
			cost += sum
			heapq.heappush(minHeap, sum)
		return cost


class Solution:

	def minCost(self, arr, n):
		heapq.heapify(arr)
		global_cost = 0
		while arr:
			a = heapq.heappop(arr)
			if arr:
				b = heapq.heappop(arr)
			else:
				return global_cost
			local_cost = a + b
			global_cost += local_cost
			heapq.heappush(arr, local_cost)
		return global_cost


import heapq

class Solution:

	def minCost(self, arr, n):
		heapq.heapify(arr)
		res = 0
		while len(arr) > 1:
			m1 = heapq.heappop(arr)
			m2 = heapq.heappop(arr)
			res += m1 + m2
			heapq.heappush(arr, m1 + m2)
		return res


from heapq import *

class Solution:

	def minCost(self, arr, n):
		minheap = []
		for i in arr:
			heappush(minheap, i)
		ans = 0
		while len(minheap) > 1:
			x = heappop(minheap)
			y = heappop(minheap)
			heappush(minheap, x + y)
			ans += x + y
		return ans


from heapq import heappop, heappush, heapify

class Solution:

	def minCost(self, arr, n):
		sumi = 0
		heapify(arr)
		while len(arr) > 1:
			a = heappop(arr)
			b = heappop(arr)
			heappush(arr, a + b)
			sumi += a + b
		return sumi


class Solution:

	def minCost(self, arr, n):
		import heapq as hq
		hq.heapify(arr)
		ans = 0
		if len(arr) < 2:
			return 0
		while len(arr) > 1:
			l1 = hq.heappop(arr)
			l2 = hq.heappop(arr)
			rope_sum = l1 + l2
			hq.heappush(arr, rope_sum)
			ans += rope_sum
		return ans


import heapq

class Solution:

	def minCost(self, arr, n):
		h = []
		for i in arr:
			heapq.heappush(h, i)
		cost = 0
		while len(h) >= 2:
			i1 = heapq.heappop(h)
			i2 = heapq.heappop(h)
			item = i1 + i2
			cost += item
			heapq.heappush(h, item)
		return cost


import heapq

class Solution:

	def minCost(self, arr, n):
		(sum1, sum2, count) = (0, 0, 0)
		heap_arr = []
		heapq.heapify(arr)
		while len(arr) >= 2:
			sum1 = heapq.heappop(arr) + heapq.heappop(arr)
			sum2 += sum1
			heapq.heappush(arr, sum1)
		return sum2


import heapq

class Solution:

	def minCost(self, arr, n):
		(sum1, sum2, count) = (0, 0, 0)
		heap_arr = []
		heapq.heapify(arr)
		for j in range(n):
			count += 1
			if count == 2:
				while count:
					sum1 += heapq.heappop(arr)
					count -= 1
				sum2 += sum1
				heapq.heappush(arr, sum1)
				count += 1
				sum1 = 0
		return sum2


import heapq as hq

class Solution:

	def minCost(self, arr, n):
		l = []
		heapq.heapify(arr)
		while len(arr) != 1:
			a = heapq.heappop(arr)
			b = heapq.heappop(arr)
			l.append(a + b)
			arr.append(a + b)
		return sum(l)


import heapq

class Solution:

	def minCost(self, arr, n):
		if n == 1:
			return 0
		heapq.heapify(arr)
		cost = 0
		global_cost = 0
		while len(arr) > 1:
			a = heapq.heappop(arr)
			b = heapq.heappop(arr)
			cost = a + b
			global_cost += cost
			heapq.heappush(arr, cost)
		return global_cost


import heapq

class Solution:

	def minCost(self, arr, n):
		heapq.heapify(arr)
		cost = 0
		while len(arr) > 1:
			temp1 = heapq.heappop(arr)
			temp2 = heapq.heappop(arr)
			new = temp1 + temp2
			cost += new
			heapq.heappush(arr, new)
		return cost


import heapq

class Solution:

	def minCost(self, arr, n):
		heapq.heapify(arr)
		s = 0
		while len(arr) > 1:
			s1 = heapq.heappop(arr)
			s2 = heapq.heappop(arr)
			temp = s1 + s2
			s += temp
			heapq.heappush(arr, temp)
		return s


import heapq

class Solution:

	def minCost(self, arr, n):
		l1 = []
		heapq.heapify(arr)
		while len(arr) > 1:
			m1 = heapq.heappop(arr)
			m2 = heapq.heappop(arr)
			sum1 = m1 + m2
			l1.append(sum1)
			heapq.heappush(arr, sum1)
		return sum(l1)


from heapq import heapify, heappop, heappush

class Solution:

	def minCost(self, arr, n):
		if n == 1:
			return 0
		h = []
		heapify(h)
		for i in arr:
			heappush(h, i)
		cost = 0
		while len(h) >= 2:
			el = heappop(h) + heappop(h)
			cost += el
			heappush(h, el)
		return cost


import heapq

class Solution:

	def minCost(self, arr, n):
		heapq.heapify(arr)
		fans = 0
		while len(arr) > 1:
			ans = 0
			for i in range(2):
				ans = ans + heapq.heappop(arr)
			arr.append(ans)
			fans = fans + ans
		return fans


from heapq import *

class Solution:

	def minCost(self, arr, n):
		heapify(arr)
		s = 0
		while True:
			if len(arr) < 2:
				return s
			x = heappop(arr)
			y = heappop(arr)
			z = x + y
			s += z
			heappush(arr, z)
		return -1


import heapq as hq

class Solution:

	def minCost(self, arr, n):
		hq.heapify(arr)
		ans = 0
		while len(arr) > 1:
			min1 = hq.heappop(arr)
			ans += min1
			min2 = hq.heappop(arr)
			ans += min2
			hq.heappush(arr, min1 + min2)
		return ans


class Solution:

	def minCost(self, arr, n):
		sum = 0
		cost = 0
		minHeap = arr[:]
		heapq.heapify(minHeap)
		while len(minHeap) >= 2:
			sum = 0
			a = heapq.heappop(minHeap)
			b = heapq.heappop(minHeap)
			sum = a + b
			heapq.heappush(minHeap, sum)
			cost += sum
		return cost


import heapq

class Solution:

	def minCost(self, arr, n):
		heapq.heapify(arr)
		summ = 0
		while len(arr) > 1:
			x = heapq.heappop(arr)
			y = heapq.heappop(arr)
			z = x + y
			summ = summ + z
			heapq.heappush(arr, z)
		return summ


import heapq

class Solution:

	def minCost(self, arr, n):
		heap = arr[:]
		heapq.heapify(heap)
		total_cost = 0
		while len(heap) > 1:
			rope1 = heapq.heappop(heap)
			rope2 = heapq.heappop(heap)
			joined_rope = rope1 + rope2
			total_cost += joined_rope
			heapq.heappush(heap, joined_rope)
		return total_cost


import heapq

class Solution:

	def minCost(self, arr, n):
		cost = 0
		heapq.heapify(arr)
		while len(arr) > 1:
			rope1 = heapq.heappop(arr)
			rope2 = heapq.heappop(arr)
			cost += rope1 + rope2
			heapq.heappush(arr, rope1 + rope2)
		return cost


import heapq

class Solution:

	def minCost(self, arr, n):
		min_cost = 0
		heapq.heapify(arr)
		while len(arr) > 1:
			min1 = heapq.heappop(arr)
			min2 = heapq.heappop(arr)
			min_cost += min1 + min2
			heapq.heappush(arr, min1 + min2)
		return min_cost


import heapq as hq

class Solution:

	def minCost(self, arre, n):
		summ = 0
		arr = []
		for i in arre:
			hq.heappush(arr, i)
		while len(arr) > 1:
			v1 = hq.heappop(arr)
			v2 = hq.heappop(arr)
			summ += v1 + v2
			hq.heappush(arr, v1 + v2)
		return summ


class Solution:

	def minCost(self, arr, n):
		heap = []
		for num in arr:
			heapq.heappush(heap, num)
		cost = 0
		while len(heap) > 1:
			rope1 = heapq.heappop(heap)
			rope2 = heapq.heappop(heap)
			cur = rope1 + rope2
			cost += cur
			heapq.heappush(heap, cur)
		return cost


class Solution:

	def minCost(self, arr, n):
		min_heap = []
		for num in a:
			heapq.heappush(min_heap, num)
		total_cost = 0
		while len(min_heap) > 1:
			val_1 = heapq.heappop(min_heap)
			val_2 = heapq.heappop(min_heap)
			val = val_1 + val_2
			total_cost += val
			heapq.heappush(min_heap, val)
		return total_cost


import heapq

class Solution:

	def minCost(self, arr, n):
		return self.min_rope_join_cost(arr, n)

	def min_rope_join_cost(self, heap, heap_size):
		cost = 0
		heapq.heapify(heap)
		while len(heap) > 1:
			first_rope_length = heapq.heappop(heap)
			second_rope_length = heapq.heappop(heap)
			new_rope_length = first_rope_length + second_rope_length
			cost += new_rope_length
			heapq.heappush(heap, new_rope_length)
		return cost


class Solution:

	def minCost(self, arr, n):
		t_cost = 0
		hp = []
		heapq.heapify(hp)
		for i in arr:
			heapq.heappush(hp, i)
		while len(hp) > 1:
			currcost = heapq.heappop(hp) + heapq.heappop(hp)
			t_cost += currcost
			heapq.heappush(hp, currcost)
		return t_cost


class Solution:

	def minCost(self, arr, n):
		min_heap = []
		for i in arr:
			heapq.heappush(min_heap, i)
		cost = 0
		while len(min_heap) >= 2:
			first = heapq.heappop(min_heap)
			second = heapq.heappop(min_heap)
			temp = first + second
			cost += temp
			heapq.heappush(min_heap, temp)
		return cost


import heapq

class Solution:

	def minCost(self, arr, n):
		heapq.heapify(arr)
		cost = 0
		if len(arr) == 1:
			return 0
		while arr:
			r1 = heapq.heappop(arr)
			r2 = heapq.heappop(arr)
			i = r1 + r2
			if arr:
				heapq.heappush(arr, i)
				cost = cost + i
			else:
				cost = cost + i
				return cost
		return cost


import heapq as hq

class Solution:

	def minCost(self, arr, n):
		hq.heapify(arr)
		sum = 0
		while len(arr) != 1:
			x = hq.heappop(arr)
			y = hq.heappop(arr)
			sum += x + y
			hq.heappush(arr, x + y)
		return sum


import heapq

class Solution:

	def minCost(self, arr, n):
		heap = []
		for ele in arr:
			heapq.heappush(heap, ele)
		sum = 0
		while len(heap) > 1:
			a = heapq.heappop(heap)
			b = heapq.heappop(heap)
			sum += a + b
			heapq.heappush(heap, a + b)
		return sum


class Solution:

	def minCost(self, arr, n):
		mini = []
		for i in range(n):
			heapq.heappush(mini, arr[i])
		(ans, temp) = (0, 0)
		while n > 1:
			for i in range(2):
				ans += heapq.heappop(mini)
			heapq.heappush(mini, ans)
			temp += ans
			ans = 0
			n -= 1
		return temp


import heapq

class Solution:

	def minCost(self, arr, n):
		heap = []
		cost = 0
		for i in range(len(arr)):
			heapq.heappush(heap, arr[i])
		num1 = num2 = 0
		while heap:
			if len(heap) == 1:
				break
			num1 = heapq.heappop(heap)
			num2 = heapq.heappop(heap)
			cost += num1 + num2
			heapq.heappush(heap, num1 + num2)
		return cost


import heapq

class Solution:

	def minCost(self, array, n):
		if len(array) == 1:
			return 0
		heap = []
		for item in array:
			heapq.heappush(heap, item)
		answer = 0
		while len(heap) != 1:
			rope1 = heapq.heappop(heap)
			rope2 = heapq.heappop(heap)
			cost = rope1 + rope2
			heapq.heappush(heap, cost)
			answer += cost
		return answer


import heapq

class Solution:

	def minCost(self, arr, n):
		h = []
		cost = 0
		for i in range(n):
			heapq.heappush(h, arr[i])
		while len(h) > 1:
			(f, s) = (heapq.heappop(h), heapq.heappop(h))
			concatcost = f + s
			cost += concatcost
			heapq.heappush(h, concatcost)
		return cost


import heapq as hq

class Solution:

	def minCost(self, arr, n):
		heap = []
		cost = 0
		for i in range(n):
			hq.heappush(heap, arr[i])
		while len(heap) > 1:
			x = hq.heappop(heap) + hq.heappop(heap)
			cost = cost + x
			hq.heappush(heap, x)
		return cost


import heapq

class Solution:

	def minCost(self, arr, n):
		ans = 0
		heapq.heapify(arr)
		for i in range(n - 1):
			a1 = heapq.heappop(arr)
			a2 = heapq.heappop(arr)
			ans += a1 + a2
			heapq.heappush(arr, a1 + a2)
		return ans


import heapq

class Solution:

	def minCost(self, arr, n):
		ans = 0
		heapq.heapify(arr)
		while len(arr) > 1:
			a1 = heapq.heappop(arr)
			a2 = heapq.heappop(arr)
			ans += a1 + a2
			heapq.heappush(arr, a1 + a2)
		return ans


import heapq

class Solution:

	def minCost(self, arr, n):
		ans = 0
		heapq.heapify(arr)
		for i in range(n - 1):
			a = heapq.heappop(arr)
			b = heapq.heappop(arr)
			c = a + b
			ans += c
			heapq.heappush(arr, c)
		return ans