You are given an array A of N elements. For any ordered triplet (i, j, k) such that i, j, and k are pairwise distinct and 1 ≤ i, j, k ≤ N, the value of this triplet is (A_{i}-A_{j})\cdot A_{k}. You need to find the maximum value among all possible ordered triplets.

Note: Two ordered triplets (a, b, c) and (d, e, f) are only equal when a = d and b = e and c = f. As an example, (1, 2, 3) and (2, 3, 1) are two different ordered triplets.

------ Input Format ------ 

- The first line of the input contains a single integer T - the number of test cases. The test cases then follow.
- The first line of each test case contains an integer N.
- The second line of each test case contains N space-separated integers A_{1}, A_{2}, \dots, A_{N}.

------ Output Format ------ 

For each test case, output the maximum value among all different ordered triplets.

------ Constraints ------ 

$1 ≤T ≤100$
$3 ≤N ≤3 \cdot 10^{5}$
$1 ≤A_{i} ≤10^{6}$
- Sum of $N$ over all testcases won't exceed $3 \cdot 10^{5}$.

------ subtasks ------ 

Subtask $1$ (30 points): Sum of $N$ over all cases won't exceed $2000$.
Subtask $2$ (70 points): Original constraint

----- Sample Input 1 ------ 
3
3
1 1 3
5
3 4 4 1 2
5
23 17 21 18 19
----- Sample Output 1 ------ 
2
12
126
----- explanation 1 ------ 
- Test case $1$: The desired triplet is $(3, 2, 1)$, which yields the value of $(A_{3} - A_{2}) \cdot A_{1} = (3 - 1) \cdot 1 = 2$.
- Test case $2$: The desired triplet is $(2, 4, 3)$, which yields the value of $(A_{2} - A_{4}) \cdot A_{3} = (4 - 1) \cdot 4 = 12$.
- Test case $3$: The desired triplet is $(1, 2, 3)$, which yields the value of $(A_{1} - A_{2}) \cdot A_{3} = (23 - 17) \cdot 21 = 126$.

Source: codechef | Difficulty: EASY
Tags: Sorting

Constructive algorithms

Ad-hoc


Solutions:
t = int(input())
for ni in range(t):
	n = int(input())
	a = [int(i) for i in input().split()]
	a.sort()
	print((a[n - 1] - a[0]) * a[n - 2])


T = int(input())
for z in range(T):
	n = int(input())
	nums = list(map(int, input().split()))
	nums.sort()
	print((nums[n - 1] - nums[0]) * nums[n - 2])


for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	a = sorted(a)
	print(max((a[-1] - a[0]) * a[-2], (a[-2] - a[0]) * a[-1]))


t = int(input())
for i in range(t):
	n = int(input())
	a = [int(c) for c in input().split()]
	a.sort()
	l = (a[n - 1] - a[0]) * a[n - 2]
	m = (a[n - 2] - a[0]) * a[n - 1]
	if l >= m:
		print(l)
	else:
		print(m)


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l.sort()
	a = l[-1]
	b = l[0]
	c = l[-2]
	print((a - b) * c)


n = int(input())
for i in range(n):
	x = int(input())
	l = list(map(int, input().split()))
	l.sort()
	print((l[x - 1] - l[0]) * l[x - 2])


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	print((a[-1] - a[0]) * a[-2])


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	r = (a[n - 1] - a[0]) * a[n - 2]
	print(r)


for _ in range(int(input())):
	n = int(input())
	l = sorted(list(map(int, input().split())), reverse=True)
	print((l[0] - l[-1]) * l[1])


t = int(input())
while t > 0:
	n = int(input())
	l = list(map(int, input().split()))
	l.sort()
	print((l[n - 1] - l[0]) * l[n - 2])
	t = t - 1


t = int(input())
for j in range(t):
	n = int(input())
	l = sorted(list(map(int, input().split(' '))))
	print((l[-1] - l[0]) * l[-2])


for _ in range(int(input())):
	(n, s) = (int(input()), sorted(list(map(int, input().split(' ')))))
	print((s[-1] - s[0]) * s[-2])


from itertools import product
for _ in range(int(input())):
	n = int(input())
	values = []
	List = sorted(list(map(int, input().split())))
	print((List[-1] - List[0]) * List[-2])


t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	l.sort()
	print((l[-1] - l[0]) * l[-2])


t = int(input())
for t in range(t):
	n = int(input())
	arr = [int(i) for i in input().split()]
	arr = sorted(arr)
	(i, j, k) = (arr[0], arr[n - 2], arr[n - 1])
	ans = max((j - i) * k, (k - i) * j)
	print(ans)


for t in range(int(input())):
	input()
	a = [int(i) for i in input().split()]
	ma = max(a)
	mi = min(a)
	if a.count(ma) > 1:
		print((ma - mi) * ma)
	else:
		a.pop(a.index(ma))
		print((ma - mi) * max(a))


for __ in range(int(input())):
	n = int(input())
	l = sorted(list(map(int, input().split())))
	(a, b, c) = (l[0], l[n - 2], l[n - 1])
	print((c - a) * b)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l = sorted(l)
	x = l[-1] - l[0]
	print(x * l[-2])


T = int(input())
for i in range(T):
	m = int(input())
	nums = list(map(int, input().split()))
	nums.sort()
	print((nums[m - 1] - nums[0]) * nums[m - 2])


for i in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	A.sort()
	print(A[N - 2] * (A[N - 1] - A[0]))


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	c = max(a)
	d = min(a)
	a.remove(c)
	a.remove(d)
	print((c - d) * max(a))


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l.sort()
	r1 = (l[len(l) - 2] - l[0]) * l[len(l) - 1]
	r2 = (l[len(l) - 1] - l[0]) * l[len(l) - 2]
	print(max(r1, r2))


for x in range(int(input())):
	n = int(input())
	a = [int(d) for d in input().split()]
	a.sort()
	x = a[-1]
	y = a[0]
	z = a[-2]
	print((x - y) * z)


t = int(input())
for i in range(t):
	n = int(input())
	ar = list(map(int, input().split()))
	maxi = max(ar)
	ar.pop(ar.index(maxi))
	mini = min(ar)
	max_2 = max(ar)
	print((maxi - mini) * max_2)


for i in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	A.sort()
	x = max(A) - min(A)
	A.remove(max(A))
	print(max(A) * x)


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	p = max(a)
	q = min(a)
	a.remove(p)
	b = max(a)
	print((p - q) * b)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	a2 = a[0]
	a3 = a[-2]
	a1 = a[-1]
	print((a1 - a2) * a3)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	print((max(a) - min(a)) * a[-2])


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	x = max(a)
	z = min(a)
	a.sort()
	y = a[-2]
	print((x - z) * y)


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	print(max((a[-1] - a[0]) * a[-2], (a[-2] - a[0]) * a[-1]))


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	(x, y, z) = (a[0], a[-2], a[-1])
	if (z - x) * y > (y - x) * z:
		print((z - x) * y)
	else:
		print((y - x) * z)


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	l.sort()
	res = (l[-1] - l[0]) * l[-2]
	print(res)


t = input()
for c in range(0, int(t)):
	n = input()
	a = input().split()
	arr = []
	for x in a:
		arr.append(int(x))
	arr.sort()
	print((arr[int(n) - 1] - arr[0]) * arr[int(n) - 2])


for i in range(int(input())):
	n = int(input())
	li = list(map(int, input().split(' ')))
	li.sort()
	print(li[n - 2] * (li[n - 1] - li[0]))


for _ in range(int(input())):
	lenn = int(input())
	l = list(map(int, input().split()))
	a = max(l)
	l.remove(a)
	b = max(l)
	c = min(l)
	print((a - c) * b)


def max_trio(array, length):
	biggest = 0
	second_biggest = 0
	smallest = array[0]
	temporary_array = array
	temporary_array.sort()
	smallest = temporary_array[0]
	biggest = temporary_array[-1]
	second_biggest = temporary_array[-2]
	case1 = (second_biggest - smallest) * biggest
	case2 = (biggest - smallest) * second_biggest
	if case1 > case2:
		print(case1)
	else:
		print(case2)
T = int(input())
for i in range(0, T):
	length = int(input())
	array = input().split(' ')
	array = [int(x) for x in array]
	max_trio(array, length)


def mergeSort(arr):
	length = len(arr)
	if length > 1:
		mid = length // 2
		l = arr[:mid]
		r = arr[mid:]
		mergeSort(l)
		mergeSort(r)
		l_length = mid
		r_length = length - mid
		l_idx = r_idx = i = 0
		while l_idx < l_length and r_idx < r_length:
			if l[l_idx] <= r[r_idx]:
				arr[i] = l[l_idx]
				l_idx += 1
			else:
				arr[i] = r[r_idx]
				r_idx += 1
			i += 1
		while l_idx < l_length:
			arr[i] = l[l_idx]
			l_idx += 1
			i += 1
		while r_idx < r_length:
			arr[i] = r[r_idx]
			r_idx += 1
			i += 1
t = int(input())
for _ in range(t):
	n = int(input())
	arr = [int(x) for x in input().split()]
	mergeSort(arr)
	max_triplet = (arr[-1] - arr[0]) * arr[-2]
	print(max_triplet)


for x in range(int(input())):
	n = int(input())
	a = [int(d) for d in input().split()]
	a.sort()
	data = (a[-1] - a[0]) * a[-2]
	print(data)


tests = int(input())
for i in range(tests):
	length = int(input())
	arr = list(map(int, input().split()))
	max1 = 0
	max2 = 0
	for j in arr:
		if j > max1:
			max2 = max1
			max1 = j
		elif j > max2:
			max2 = j
	print(max((max2 - min(arr)) * max1, (max1 - min(arr)) * max2))


T = int(input())
for _ in range(T):
	N = int(input())
	lst = list(map(int, input().split()))
	lst = sorted(lst)
	X = (lst[-1] - lst[0]) * lst[-2]
	print(X)


t = int(input())
while t:
	n = int(input())
	a = list(map(int, input().split(' ')))
	max_item = max(a)
	min_item = min(a)
	a.remove(max_item)
	secondMax = max(a)
	cal1 = (secondMax - min_item) * max_item
	cal2 = (max_item - min_item) * secondMax
	if cal1 > cal2:
		print(cal1)
	else:
		print(cal2)
	t -= 1


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	arr.sort()
	ans = (arr[n - 1] - arr[0]) * arr[n - 2]
	print(ans)


import math
t = int(input())
for _ in range(t):
	n = map(int, input().split())
	cities = list(map(int, input().split()))
	cities.sort(reverse=True)
	if cities[0] * (cities[1] - cities[-1]) >= cities[1] * (cities[0] - cities[-1]):
		print(cities[0] * (cities[1] - cities[-1]))
	else:
		print(cities[1] * (cities[0] - cities[-1]))


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	k = sorted(l)[::-1]
	print((k[0] - k[-1]) * k[1])


t = int(input())
while t:
	n = int(input())
	li = list(map(int, input().split()))
	s = max(li)
	s1 = min(li)
	li.remove(max(li))
	s2 = max(li)
	ans = (s - s1) * s2
	print(ans)
	t -= 1


for t in range(int(input())):
	n = int(input())
	arr = [int(char) for char in input().split()]
	l1 = max(arr)
	l2 = min(arr)
	arr.remove(l1)
	l3 = max(arr)
	print((l1 - l2) * l3)


for tc in range(int(input())):
	n = int(input())
	A = list(map(int, input().split()))
	A.sort()
	print(max((A[n - 1] - A[0]) * A[n - 2], (A[n - 2] - A[0]) * A[n - 1]))


for i in range(int(input())):
	n = int(input())
	ar = list(map(int, input().split()))
	ar.sort()
	b = max(ar)
	m = min(ar)
	c = ar.count(b)
	if c > 1:
		print((b - m) * b)
	elif c == 1:
		print((b - m) * ar[n - 2])


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	a = []
	for j in range(n):
		a.append(l[j])
	a.sort()
	print((a[len(a) - 1] - a[0]) * a[len(a) - 2])


for _ in range(int(input())):
	n = int(input())
	arr = [int(i) for i in input().split()]
	arr.sort()
	ans = (arr[-1] - arr[0]) * arr[-2]
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	l = sorted(a)
	ans = (l[-1] - l[0]) * l[-2]
	print(ans)


for i in range(int(input())):
	n = int(input())
	x = list(map(int, input().split()))
	x = sorted(x)
	h = (x[-1] - x[0]) * x[-2]
	print(h)


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	if n == 1 or n == 2:
		print(0)
	else:
		x = max(a)
		a.remove(x)
		print((x - min(a)) * max(a))


testcase = int(input())
while testcase > 0:
	testcase -= 1
	n = int(input())
	arr = list(map(int, input().split()))
	arr.sort()
	print((arr[-1] - arr[0]) * arr[-2])


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	k = max(a) - min(a)
	a.remove(max(a))
	a.remove(min(a))
	print(k * max(a))


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort(reverse=True)
	print(max(a[0] * (a[1] - a[-1]), a[1] * (a[0] - a[-1])))


T = int(input())
for i in range(T):
	N = int(input())
	A = [j for j in map(int, input().split(' '))]
	max1 = max(A)
	A.remove(max1)
	max2 = max(A)
	min1 = min(A)
	print(max((max1 - min1) * max2, (max2 - min1) * max1))


for _ in range(int(input())):
	n = int(input())
	l1 = list(map(int, input().split()))
	l1.sort()
	i = l1[0]
	j = l1[n - 2]
	k = l1[n - 1]
	k1 = k * (j - i)
	k2 = j * (k - i)
	print(max(k1, k2))


t = int(input())
while t:
	n = int(input())
	a = [int(i) for i in input().split()]
	a.sort()
	print((a[-1] - a[0]) * a[-2])
	t -= 1


t = int(input())
while t:
	n = int(input())
	arr = list(map(int, input().split()))
	arr.sort()
	a = arr[-1]
	b = arr[-2]
	c = arr[0]
	print((a - c) * b)
	t -= 1


t = int(input())
for i in range(t):
	a = int(input())
	b = list(map(int, input().split()))
	maxa = max(b)
	minb = min(b)
	b.remove(maxa)
	maxa1 = max(b)
	print((maxa - minb) * maxa1)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	(ma, mi) = (arr[0], arr[0])
	m_i = 0
	for i in range(n):
		if arr[i] > ma:
			ma = arr[i]
			m_i = i
		elif arr[i] < mi:
			mi = arr[i]
	p = mi
	for i in range(n):
		if i != m_i and arr[i] > p:
			p = arr[i]
	print((ma - mi) * p)


x = int(input())
while x > 0:
	N = int(input())
	arr = list(map(int, input().split()))
	v = max(arr)
	arr.remove(max(arr))
	v = v - min(arr)
	v = v * max(arr)
	print(v)
	x = x - 1