breaking-bad-3

“All Hail The King.”

Middle aged, and overqualified highschool chemistry teacher Walter White has been diagnosed with lung cancer. To make sure his family is financially secure, he teams up with a former student Jesse Pinkman and turns to a life of crime to make and distribute the purest crystal meth on the streets.

In order to cook crystal meth Jesse has collected a total of N ingredients. Each ingredient is bought at a price of Ai dollars.
The procedure for cooking crystal meth goes as follows:
     Walter starts with an empty round bottom flask. He then selects any two ingredients and adds them together at the same time in the flask. Then he selects another pair of ingredients and adds them. He keeps adding pairs of ingredients till all the ingredients have been added.

When a pair of ingredients i, j are added together at the same time, their total value is given by the product of Ai and Aj .
The street value of the crystal meth prepared by the above procedure is given by the sum of (Ai * Aj) over all pairs of i,j that are added at the same time.
You are given the number of ingredients (N) and the price at which these ingredients are bought (A1,A2,...,An).

You need to help Walter find the maximum possible street value of the crystal meth prepared using the above method.
Note: An ingredient can be added only once.

Input:

The first line will contain an integer T denoting the number of testcases.
For each test case, there will be 2 lines.
The first line will contain N, the number of ingredients (N is always even).
In the next line, there will be N space-separated integers A1,A2,...,An. Integer Ai  denotes the price at which the i^th ingredient is bought.

Output:

For each test case, print the maximum possible street value of the crystal meth prepared using the above method.

Constraints:
1 ≤ T ≤ 10
2 ≤ N ≤ 2*10^5
1 ≤ Ai ≤ 10^6

SAMPLE INPUT
2
2
3 1
4
1 4 6 3

SAMPLE OUTPUT
3
27

Explanation

1st case:
There is only 1 pair of integers (3 and 1) therefore the maximum possible street value will be (3*1) that is 3.

2nd case:
To get the maximum possible street value walter first selects 2nd & 3rd ingredient product of which is 24. He then selects the remaining two ingredients with product 3. The total street value is therefore 24+3 = 27.
Note: Alternatively, Walter can select 3,1 first and then 4,6 which will also give 27.

Difficulty: EASY

Starter code:

Solutions:
t = int(input())
for i in range(t):
	N = int(input())
	a = list(map(int, input().split()))
	a.sort()
	sum = 0
	for i in range(0, N, 2):
		if i <= N - 2:
			sum += a[i] * a[i + 1]
	print(sum)


#from operator import itemgetter

T = eval(input())

for i in range(0,T):
    
	N = eval(input())
	A= []
	A.append(input().split())
	A = [int(x) for x in A[0]]

	#print A

	sum1 = 0
	c = 1
	#A=sorted(A, key=itemgetter(0))
	len1 = len(A)
	A.sort()
	for i in range(0,N/2):
		
		a = A[len1- c]
		c = c+1
		#A.remove(a)
		b = A[len1- c]
		c = c + 1
		#A.remove(b)
		#print A
		sum1 = sum1 + (a*b)
	print(sum1)

		
##    sum1 = 0
##    for i in range(0,N/2):
##        a = max(A)
##        A.remove(a)
##        #print A
##        b = max(A)
##        A.remove(b)
##        sum1 = sum1 + (a*b)
	
		


t=eval(input())
for k in range(t):
	ans=0
	n=eval(input())
	s=list(map(int, input().split()))
	s=sorted(s)
	i=0
	while(i<n):
		ans+=s[i]*s[i+1]
		i+=2
	print(ans)


import sys
f=sys.stdin
x=int(f.readline())
array=[]
score=0
k=1
for d in range(0,x):
	s=int(f.readline())
	line=f.readline()
	for x in line.split():
		array.append(int(x))
	array.sort()
	while k<s:
		score=score+array[k-1]*array[k]
		k=k+2
	sys.stdout.write(str(score)+'\n')
	array[:]=[]
	k=1
	score=0



for _ in range(int(input())):
	n=int(input())
	a=list(map(int,input().split()))
	a=sorted(a,reverse=True)
	add=0
	i=0
	l=len(a)
	while i<l:
		add=add+(a[i]*a[i+1])
		i+=2
	print(add)
		


import sys
f=sys.stdin
x=int(f.readline())
array=[]
score=0
k=1
for d in range(0,x):
	s=int(f.readline())
	line=f.readline()
	for x in line.split():
		array.append(int(x))
	array.sort()
	while k<s:
		score=score+array[k-1]*array[k]
		k=k+2
	sys.stdout.write(str(score)+'\n')
	array[:]=[]
	k=1
	score=0