Given an array of even size consisting of positive integers. Your task is to find the sum after sorting the array, such that the sum of product of alternate elements is minimum.
 
Example 1:
Input:
8
9 2 8 4 5 7 6 0
Output:
74
Explanation:
Required sum can be obtained as
9*0 + 8*2 + 7*4 + 6*5 which
is equal to 74.
 
Example 2:
Input:
4
1 2 3 4
Output:
10
Explanation:
1*4 + 2*3 = 10
 
Your Task:  
You don't need to read input or print anything. Your task is to complete the function altPoduct() which takes the array A[] and its size N as inputs and returns the minimum sum.
Expected Time Complexity: O(N. log(N))
Expected Auxiliary Space: O(1)
 
Constraints:
2 ≤ N ≤ 10^{5}
1 ≤ A_{i} ≤ 10^{7}
N is always even

Difficulty: EASY
Tags: Sorting

Data structures
Skill types: Sorting

Data structures
Expected Time Complexity: O(N. log(N))
Expected Auxiliary Space: O(1)

Starter code:
#User function Template for python3



def altProduct( arr, n):

    # Your code goes here 





Solutions:
def altProduct(arr, n):
	arr.sort()
	summ = 0
	for i in range(len(arr) // 2):
		summ += arr[i] * arr[-(i + 1)]
	return summ


def altProduct(arr, n):
	arr.sort()
	start = 0
	end = n - 1
	sumi = 0
	mid = int(n / 2)
	for i in range(mid):
		sumi += arr[start] * arr[end]
		start += 1
		end -= 1
	return sumi


def altProduct(arr, n):
	arr.sort()
	product = 0
	for i in range(n // 2):
		product += arr[i] * arr[n - 1]
		i = i + 1
		n = n - 1
	return product


def altProduct(arr, n):
	arr1 = sorted(arr)
	m = 0
	k = n - 1
	prod = 0
	for i in range(n // 2):
		prod = prod + arr1[m] * arr1[k]
		m += 1
		k -= 1
	return prod


def altProduct(arr, n):
	arr.sort()
	a = 0
	i = 0
	j = n - 1
	while i < j:
		b = int(arr[i] * arr[j])
		a += b
		i += 1
		j -= 1
	return a


def altProduct(arr, n):
	total = 0
	i = 0
	j = n - 1
	arr.sort()
	while i < j:
		total += arr[i] * arr[j]
		j = j - 1
		i = i + 1
	return total


def altProduct(arr, n):
	arr.sort()
	(i, j) = (0, n - 1)
	ans = 0
	while i < j:
		ans += arr[i] * arr[j]
		i += 1
		j -= 1
	return ans


def altProduct(arr, n):
	arr.sort()
	l = 0
	r = n - 1
	s = []
	while l < r:
		if l < r:
			s.append(arr[l] * arr[r])
		l += 1
		r -= 1
	return sum(s)


def altProduct(arr, n):
	arr.sort()
	i = 0
	j = n - 1
	op = 0
	while i <= j:
		op += arr[i] * arr[j]
		i += 1
		j -= 1
	return op


def altProduct(arr, n):
	arr.sort()
	half = arr[n // 2:]
	half.reverse()
	min_sum = 0
	for i in range(len(half)):
		min_sum += half[i] * arr[i]
	return min_sum


def altProduct(arr, n):
	arr.sort()
	l = []
	sum = 0
	for i in range(n // 2):
		s = arr[i] * arr[n - (i + 1)]
		l.append(s)
		sum += l[i]
	return sum


def altProduct(arr, n):
	arr.sort()
	f = 0
	l = n - 1
	prod = 0
	for i in range(n // 2):
		prod += arr[f] * arr[l]
		f += 1
		l -= 1
	return prod


def altProduct(arr, n):
	a = 0
	x = 1
	arr.sort()
	for i in range(n // 2):
		a += arr[i] * arr[-x]
		x += 1
	return a


def altProduct(arr, n):
	arr.sort()
	sum_ = 0
	start = 0
	end = n - 1
	while start < end:
		sum_ += arr[start] * arr[end]
		start += 1
		end -= 1
	return sum_


def altProduct(arr, n):
	arr.sort()
	(i, j) = (0, n - 1)
	summ = 0
	for b in range(n // 2):
		summ = summ + arr[i] * arr[j]
		i += 1
		j -= 1
	return summ


def altProduct(arr, n):
	arr.sort()
	s = 0
	for index in range(n // 2):
		s += arr[index] * arr[n - index - 1]
	return s


def altProduct(arr, n):
	asc = sorted(arr)
	desc = sorted(arr, reverse=True)
	sum = 0
	for i in range(n // 2):
		sum += asc[i] * desc[i]
	return sum


def altProduct(arr, n):
	even = []
	odd = []
	arr.sort()
	for i in range(n):
		if i < n // 2:
			odd.append(arr[i])
		else:
			even.append(arr[i])
	even.sort(reverse=True)
	i = 0
	sum = 0
	for j in range(len(even)):
		arr[i] = even[j]
		i += 1
		arr[j] = odd[j]
		i += 1
		sum += even[j] * odd[j]
	return sum


def altProduct(arr, n):
	arr.sort()
	left = 0
	right = n - 1
	sum = 0
	while right > left:
		sum += arr[left] * arr[right]
		left += 1
		right -= 1
	return sum


def altProduct(arr, n):
	arr.sort()
	i = 0
	j = n - 1
	s = 0
	while i < j:
		s = s + arr[i] * arr[j]
		i = i + 1
		j = j - 1
	return s


def altProduct(arr, n):
	l1 = []
	l2 = []
	count = 0
	arr.sort()
	k = n // 2
	l1.extend(arr[k:])
	l2.extend(arr[:k])
	arr.clear()
	arr.extend(l1[::-1])
	for i in range(k):
		count += arr[i] * l2[i]
	return count


def altProduct(arr, n):
	arr.sort()
	sum = 0
	j = len(arr) - 1
	for i in range(0, int(n / 2)):
		sum = sum + arr[i] * arr[j]
		i += 1
		j -= 1
	return sum


def altProduct(arr, n):
	arr.sort()
	k1 = arr[0:n // 2]
	k2 = arr[n // 2:]
	k2.reverse()
	k = 0
	for i in range(n // 2):
		k = k + k1[i] * k2[i]
	return k


def altProduct(arr, n):
	arr = sorted(arr)
	prod = 0
	for i in range(n // 2):
		prod = prod + arr[i] * arr[-i - 1]
	return prod


def mergesort(arr):
	if len(arr) > 1:
		mid = len(arr) // 2
		L = arr[:mid]
		R = arr[mid:]
		mergesort(L)
		mergesort(R)
		i = k = j = 0
		while i < len(L) and j < len(R):
			if L[i] < R[j]:
				arr[k] = L[i]
				i += 1
			else:
				arr[k] = R[j]
				j += 1
			k += 1
		while i < len(L):
			arr[k] = L[i]
			i += 1
			k += 1
		while j < len(R):
			arr[k] = R[j]
			k += 1
			j += 1

def altProduct(arr, n):
	mergesort(arr)
	sumo = 0
	for i in range(n // 2):
		sumo += arr[i] * arr[-i - 1]
	return sumo


def altProduct(arr, n):
	arr.sort()
	sum = 0
	i = 0
	l = []
	while len(l) < len(arr):
		l.append(arr[i])
		l.append(arr[len(arr) - 1 - i])
		sum += arr[i] * arr[len(arr) - 1 - i]
		i += 1
	return sum


def altProduct(arr, n):
	l = []
	arr.sort()
	i = 0
	j = n - 1
	while i < j:
		l.append(arr[j])
		l.append(arr[i])
		j = j - 1
		i = i + 1
	p = 0
	for i in range(0, n - 1, 2):
		p = p + l[i] * l[i + 1]
	return p


def altProduct(arr, n):
	k = sorted(arr)
	k1 = k[:n // 2]
	k2 = k[n // 2:][::-1]
	s = 0
	for i in range(len(k1)):
		s += k1[i] * k2[i]
	return s


def altProduct(arr, n):
	a = sorted(arr)
	x = []
	for i in range(n):
		x.append(a[i] * a[-i - 1])
	k = len(x) // 2
	return sum(x[:k])


def altProduct(a, n):
	s = 0
	a = sorted(a)
	for i in range(n // 2):
		s = s + a[i] * a[n - i - 1]
	return s


def altProduct(arr, n):
	arr.sort()
	l = n // 2
	a = arr[0:l]
	b = arr[l:]
	r = 0
	for i in range(l):
		res = a[i] * b[-(i + 1)]
		r = r + res
	return r


def altProduct(arr, n):
	arr.sort()
	fr = 0
	en = n - 1
	s = 0
	for j in range(n // 2):
		s += arr[fr] * arr[en]
		fr += 1
		en -= 1
	return s


def altProduct(arr, n):
	arr.sort()
	res = 0
	l = 0
	h = n - 1
	while l < h:
		res += arr[l] * arr[h]
		h -= 1
		l += 1
	return res


def altProduct(arr, n):
	sum = 0
	arr.sort()
	low = 0
	high = n - 1
	while low < high:
		sum += arr[low] * arr[high]
		high -= 1
		low += 1
	return sum


def altProduct(arr, n):
	arr.sort()
	return sum((arr[i] * arr[-i - 1] for i in range(n // 2)))


def altProduct(arr, n):
	start = 0
	end = n - 1
	sum = 0
	arr.sort()
	while start < end:
		k = arr[start]
		m = arr[end]
		start += 1
		end -= 1
		mul = k * m
		sum += mul
	return sum


def altProduct(arr, n):
	arr.sort()
	tot = 0
	low = 0
	high = n - 1
	while low <= high:
		tot += arr[int(low)] * arr[int(high)]
		low += 1
		high -= 1
	return tot


def altProduct(arr, n):
	arr.sort()
	l = 0
	r = n - 1
	su = 0
	while r > l:
		su += arr[l] * arr[r]
		l += 1
		r -= 1
	return su


def altProduct(arr, n):
	arr = sorted(arr)
	l = []
	k = []
	for i in range(n // 2):
		l.append(arr[i])
	for i in range(n // 2, n):
		k.append(arr[i])
	k = k[::-1]
	i = 0
	j = 0
	m = []
	while i < len(l) and j < len(k):
		m.append(l[i])
		m.append(k[j])
		i += 1
		j += 1
	while i < len(l):
		m.append(l[i])
		i += 1
	while j < len(k):
		m.append(k[j])
		j += 1
	s = 0
	for i in range(0, n - 1, 2):
		s += m[i] * m[i + 1]
	return s


def altProduct(arr, n):
	arr.sort()
	start = 0
	end = n - 1
	product = 0
	while start < end:
		product += arr[start] * arr[end]
		start = start + 1
		end = end - 1
	return product


def altProduct(arr, n):
	arr.sort()
	m = 0
	k = n - 1
	pro = 0
	for i in range(n // 2):
		pro = pro + arr[m] * arr[k]
		m += 1
		k -= 1
	return pro


def altProduct(arr, n):
	arr.sort()
	l = 0
	r = n - 1
	sum1 = 0
	while l < r:
		sum1 += arr[l] * arr[r]
		l += 1
		r -= 1
	return sum1


def altProduct(arr, n):
	arr.sort()
	low = 0
	high = n - 1
	res = 0
	while low < high:
		res = res + arr[low] * arr[high]
		high -= 1
		low += 1
	return res


def altProduct(arr, n):
	arr.sort()
	l = 0
	r = n - 1
	sum = 0
	while l < r:
		sum += arr[l] * arr[r]
		l += 1
		r -= 1
	return sum


def altProduct(arr, n):
	a = arr.sort(reverse=True)
	l = 0
	r = len(arr) - 1
	s = 0
	while l < r:
		s += arr[l] * arr[r]
		l += 1
		r -= 1
	return s


def altProduct(arr, n):
	arr.sort()
	(i, j) = (0, n - 1)
	p = 0
	while i < j:
		p += arr[i] * arr[j]
		i += 1
		j -= 1
	return p


def altProduct(arr, n):
	arr.sort()
	count = 0
	a = 0
	b = n - 1
	while a < b:
		count += arr[a] * arr[b]
		a += 1
		b -= 1
	return count


def altProduct(arr, n):
	arr.sort()
	x = arr[:n // 2]
	y = arr[n // 2:][::-1]
	count = 0
	for i in range(n // 2):
		count += x[i] * y[i]
	return count


def altProduct(arr, n):
	arr.sort()
	i = 0
	j = n - 1
	su = 0
	while i < j:
		su += arr[i] * arr[j]
		i += 1
		j -= 1
	return su


def altProduct(arr, n):
	arr.sort()
	b = arr.copy()
	arr.reverse()
	c = 0
	for i in range(n):
		if n == 0:
			break
		else:
			c += arr[i] * b[i]
			n -= 2
	return c


def altProduct(arr, n):
	arr.sort()
	i = 0
	j = n - 1
	sum1 = 0
	while i < j:
		sum1 = sum1 + arr[j] * arr[i]
		i = i + 1
		j = j - 1
	return sum1


def altProduct(arr, n):
	arr.sort()
	l = n // 2
	a1 = arr[0:l]
	a2 = arr[l:n]
	a2 = a2[::-1]
	p = 0
	for i in range(l):
		p = p + a1[i] * a2[i]
	return p


def altProduct(arr, n):
	arr.sort()
	l = len(arr)
	sum = 0
	for i in range(0, l // 2):
		sum += arr[i] * arr[l - i - 1]
	return sum


def altProduct(arr, n):
	arr.sort()
	arr1 = arr[:n // 2]
	arr2 = arr[n // 2:]
	s = 0
	for i in range(n // 2):
		s += arr1[i] * arr2[n // 2 - i - 1]
	return s


def altProduct(arr, n):
	arr.sort()
	sum = 0
	i = 0
	j = n - 1
	while i <= j:
		sum += arr[i] * arr[j]
		i = i + 1
		j = j - 1
	return sum


def altProduct(arr, n):
	arr1 = sorted(arr)
	m = 0
	k = n - 1
	prod = 0
	for i in range(n // 2):
		prod = prod + arr1[m] * arr1[k]
		m += 1
		k -= 1
	return prod

def main():
	T = int(input())
	while T > 0:
		n = int(input())
		a = [int(x) for x in input().strip().split()]
		print(altProduct(a, n))
		T -= 1
if __name__ == '__main__':
	main()


def altProduct(arr, n):
	arr.sort()
	l = 0
	r = n - 1
	sum = 0
	for i in range(n // 2):
		sum += arr[l] * arr[r]
		l += 1
		r -= 1
	return sum

def main():
	T = int(input())
	while T > 0:
		n = int(input())
		a = [int(x) for x in input().strip().split()]
		print(altProduct(a, n))
		T -= 1
if __name__ == '__main__':
	main()


def altProduct(arr, n):
	arr.sort()
	s = []
	l = []
	sum = 0
	for i in range(n):
		if i < n / 2:
			s.append(arr[i])
		else:
			l.append(arr[i])
	l.reverse()
	for i in range(len(s)):
		sum = sum + s[i] * l[i]
	return sum

def main():
	T = int(input())
	while T > 0:
		n = int(input())
		a = [int(x) for x in input().strip().split()]
		print(altProduct(a, n))
		T -= 1
if __name__ == '__main__':
	main()


def altProduct(arr, n):
	arr.sort()
	i = 0
	j = n - 1
	p = 0
	while i < j:
		p += arr[i] * arr[j]
		i += 1
		j -= 1
	return p

def main():
	T = int(input())
	while T > 0:
		n = int(input())
		a = [int(x) for x in input().strip().split()]
		print(altProduct(a, n))
		T -= 1
if __name__ == '__main__':
	main()


def altProduct(arr, n):
	arr.sort()
	a1 = []
	a2 = []
	for itr in range(n // 2):
		a1.append(arr[itr])
	for itr in range(n // 2, n):
		a2.append(arr[itr])
	total = 0
	for itr in range(n // 2):
		total += a1[itr] * a2[-1 * (itr + 1)]
	return total

def main():
	T = int(input())
	while T > 0:
		n = int(input())
		a = [int(x) for x in input().strip().split()]
		print(altProduct(a, n))
		T -= 1
if __name__ == '__main__':
	main()