Read problem statements in [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

Given an array $A$ of size $N$. Find the maximum value of the expression $a * b + a - b$ where $a$ and $b$ are $2$ distinct elements of the array.

------ Input: ------

First line will contain $T$, number of testcases. Then the testcases follow. 
Each testcase contains of two lines of input.
First line will contain $N$, number of elements of the array. 
Second line contains $N$ space separated integers, elements of the array $A$. 

------ Output: ------
For each testcase, output in a single line answer to the problem.

------ Constraints  ------
$1 ≤ T ≤ 20$
$2 ≤ N ≤ 10^{5}$
$-10^{9} ≤ A_{i} ≤ 10^{9}$

----- Sample Input 1 ------ 
2

2   

2 2

3

5 3 2
----- Sample Output 1 ------ 
4

17
----- explanation 1 ------ 
Case 1: Only possible pair is $[2, 2]$ for which answer = $2 * 2 + 2 - 2$ = $4$.

Case 2: There are six possible pairs. 

For pairs $[2, 3]$ and $[3, 2]$, answer = $2 * 3 + max(2 - 3, 3 - 2)$ = $7$

For pairs $[3, 5]$ and $[5, 3]$ answer = $5 * 3 + max(3 - 5, 5 - 3)$ = $17$ and 

For the pairs $[2, 5]$ and $[5, 2]$, answer = $2 * 5 + max(2 - 5, 5 - 2)$ = $13$. 

So final answer is maximum of $\{7, 17, 13\}$ = $17$.

Source: codechef | Difficulty: MEDIUM_HARD
Tags: Sorting

Constructive algorithms

Mathematics

Ad-hoc


Solutions:
T = int(input())
for _ in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	A.sort(reverse=True)
	max_val = float('-inf')
	for i in range(N - 1):
		val = A[i] * A[i + 1] + (A[i] - A[i + 1])
		if val > max_val:
			max_val = val
	print(max_val)


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


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


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


cases = int(input())
for i in range(cases):
	size = int(input())
	array = list(map(int, input().split()))
	array.sort(reverse=True)
	print(max(array[0] * array[1] + array[0] - array[1], array[size - 1] * array[size - 2] + array[size - 2] - array[size - 1]))


for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	a = b = float('-inf')
	c = d = float('inf')
	for num in A:
		if num > a:
			b = a
			a = num
		elif num > b:
			b = num
		if num < c:
			d = c
			c = num
		elif num < d:
			d = num
	print(max(a * b + a - b, c * d + d - c))


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


from heapq import *
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	ans1 = a[0] * a[1] + (a[1] - a[0])
	ans2 = a[-1] * a[-2] + (a[-1] - a[-2])
	print(max(ans1, ans2))


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


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


class SolveQuestion:

	def solve(self):
		for t in range(int(input())):
			N = int(input())
			L = list(map(int, input().split()))
			L.sort()
			p1 = L[0] * L[1] - L[0] + L[1]
			p2 = L[0] * L[1] - L[1] + L[0]
			p3 = L[-1] * L[-2] - L[-1] + L[-2]
			p4 = L[-1] * L[-2] - L[-2] + L[-1]
			print(max(p1, p2, p3, p4))
OBJ = SolveQuestion()
OBJ.solve()


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


import math
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = a.copy()
	max1 = max(a)
	a.remove(max1)
	max2 = max(a)
	ans1 = max1 * max2 + max1 - max2
	min1 = min(b)
	b.remove(min1)
	min2 = min(b)
	ans2 = min1 * min2 + min2 - min1
	print(max(ans1, ans2))


for _ in range(int(input())):
	n = int(input())
	arr = sorted([int(x) for x in input().split()], reverse=True)
	a = arr[0]
	b = arr[1]
	c = arr[-2]
	d = arr[-1]
	ab = a * b + abs(a - b)
	cd = c * d + abs(c - d)
	ans = max(ab, cd)
	print(ans)


def fun(a, b):
	return a * b + (a - b)
for _ in range(int(input())):
	n = int(input())
	arr = sorted(list(map(int, input().split())))
	x = fun(arr[1], arr[0])
	y = fun(arr[-1], arr[-2])
	z = fun(arr[-1], arr[0])
	print(max([x, y, z]))


from math import gcd, sqrt, ceil

def ti():
	return tuple(map(int, input().split()))

def li():
	return list(map(int, input().split()))

def si():
	return input().split()

def ii():
	return int(input())

def ip():
	return input()
for tastcas in range(int(input())):
	n = ii()
	a = li()
	a.sort()
	max = a[-1] * a[-2] + (a[-1] - a[-2])
	max2 = a[0] * a[1] + (a[1] - a[0])
	if max > max2:
		print(max)
	else:
		print(max2)


T = int(input())
N = []
arr = []
for i in range(0, T):
	N.append(int(input()))
	arr.append(input().split())
for i in range(0, T):
	for j in range(0, N[i]):
		arr[i][j] = int(arr[i][j])
for i in range(0, T):
	a = arr[i]
	a.sort()
	j = N[i] - 1
	max = a[j] * a[j - 1] + (a[j] - a[j - 1])
	max2 = a[0] * a[1] + a[1] - a[0]
	if max > max2:
		print(max)
	else:
		print(max2)


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


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


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	try:
		max1 = max(l)
		l.remove(max1)
		max2 = max(l)
		l.remove(max2)
	except ValueError:
		pass
	try:
		min1 = min(l)
		l.remove(min1)
		min2 = min(l)
		l.remove(min2)
	except ValueError:
		print(max1 * max2 + max1 - max2)
		continue
	minn = min1 * min2 + min2 - min1
	maxx = max1 * max2 + max1 - max2
	if minn >= maxx:
		print(minn)
	else:
		print(maxx)


t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	arr.sort(reverse=True)
	ans1 = arr[0] * arr[1] + arr[0] - arr[1]
	ans2 = arr[-1] * arr[-2] + arr[-2] - arr[-1]
	print(max(ans1, ans2))


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


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


try:
	t = int(input())
	for i in range(t):
		n = int(input())
		arr = list(map(int, input().split()))
		arr.sort()
		max1 = arr[n - 1] * arr[n - 2] + (arr[n - 1] - arr[n - 2])
		max2 = arr[0] * arr[1] + (arr[1] - arr[0])
		print(max(max1, max2))
except:
	pass


t = int(input())
for i in range(0, t):
	n = int(input())
	arr = list(map(int, input().split()))
	n = len(arr)
	arr.sort()
	max1 = arr[n - 1] * arr[n - 2] + arr[n - 1] - arr[n - 2]
	max2 = arr[1] * arr[0] + (arr[1] - arr[0])
	ans = max(max1, max2)
	print(ans)


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


def maximumvalue(arr):
	arr.sort()
	n = len(arr)
	max1 = arr[n - 1] * arr[n - 2] + (arr[n - 1] - arr[n - 2])
	max2 = arr[1] * arr[0] + (arr[1] - arr[0])
	ans = max(max1, max2)
	return ans
t = int(input())
for _ in range(t):
	num = int(input())
	arr = list(map(int, input().split()))
	print(maximumvalue(arr))


import math

def solve(arr):
	arr.sort()
	n = len(arr)
	max1 = arr[0] * arr[1] + abs(arr[0] - arr[1])
	max2 = arr[n - 1] * arr[n - 2] + abs(arr[n - 1] - arr[n - 2])
	return max(max1, max2)
l = int(input())
res = []
for i in range(l):
	n = int(input())
	li = list(map(int, input().split(' ')))
	res.append(solve(li))
for i in res:
	print(i)


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


t = int(input())
for _ in range(t):
	N = int(input())
	a = list(map(int, input().split()))
	a.sort()
	a1 = a[1]
	b1 = a[0]
	a2 = a[-1]
	b2 = a[-2]
	x1 = a1 * b1 + a1 - b1
	x2 = a2 * b2 + a2 - b2
	print(max(x1, x2))


t = int(input())
for i in range(t):

	def solve(li):
		n = len(li)
		li.sort()
		m1 = li[n - 2] * li[n - 1] + li[n - 1] - li[n - 2]
		m2 = li[0] * li[1] + li[1] - li[0]
		return max(m1, m2)
	l = int(input())
	li = list(map(int, input().split()))
	print(solve(li))


def solve(arr, n):
	arr.sort()
	max1 = arr[n - 1] * arr[n - 2] + (arr[n - 1] - arr[n - 2])
	max2 = arr[1] * arr[0] + (arr[1] - arr[0])
	ans = max(max1, max2)
	return ans
t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	print(solve(arr, n))


def solve(arr):
	arr.sort()
	n = len(arr)
	max1 = arr[n - 1] * arr[n - 2] + (arr[n - 1] - arr[n - 2])
	max2 = arr[1] * arr[0] + (arr[1] - arr[0])
	return max(max1, max2)
t = int(input())
while t:
	n = int(input())
	l = [int(i) for i in input().split()]
	print(solve(l), end='\n')
	t -= 1


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


import math
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l.sort()
	ans1 = l[0] * l[1] + (l[1] - l[0])
	ans2 = l[-1] * l[-2] + (l[-1] - l[-2])
	print(max(ans1, ans2))


t = int(input())
while t != 0:
	n = int(input())
	arr = [int(x) for x in input().split()]
	arr.sort()
	max1 = arr[n - 1] * arr[n - 2] + (arr[n - 1] - arr[n - 2])
	max2 = arr[1] * arr[0] + (arr[1] - arr[0])
	print(max(max1, max2))
	t -= 1


def solve(arr):
	arr.sort()
	maxi1 = arr[n - 1] * arr[n - 2] + (arr[n - 1] - arr[n - 2])
	maxi2 = arr[1] * arr[0] + (arr[1] - arr[0])
	ans = max(maxi1, maxi2)
	return ans
t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	print(solve(arr))


def solve(arr, n):
	arr.sort()
	ans1 = arr[0] * arr[1] + (arr[1] - arr[0])
	ans2 = arr[n - 1] * arr[n - 2] + (arr[n - 1] - arr[n - 2])
	print(max(ans1, ans2))
t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	solve(arr, n)


def solve(n, a):
	a.sort()
	m1 = a[n - 1] * a[n - 2] + a[n - 1] - a[n - 2]
	m2 = a[0] * a[1] + a[1] - a[0]
	return max(m1, m2)
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	if n == 2:
		print(a[0] * a[1] + abs(a[0] - a[1]))
	else:
		print(solve(n, a))


t = int(input())
maxi = 0
for i in range(t):
	n = int(input())
	x = list(map(int, input().split()))
	x.sort()
	max1 = x[n - 1] * x[n - 2] + x[n - 1] - x[n - 2]
	max2 = x[1] * x[0] + x[1] - x[0]
	ans = max(max1, max2)
	print(ans)


tc = int(input())
for _ in range(tc):
	n = int(input())
	nums = list(map(int, input().split()))
	maxE = 0
	nums.sort()
	max1 = nums[n - 1] * nums[n - 2] + (nums[n - 1] - nums[n - 2])
	max2 = nums[1] * nums[0] + (nums[1] - nums[0])
	maxE = max(max1, max2)
	print(maxE)


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


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


t = int(input())
for i in range(t):
	n = int(input())
	lst = list(map(int, input().split()))
	lst.sort()
	max1 = lst[-1]
	max2 = lst[-2]
	val = max1 * max2 + max1 - max2
	max1 = lst[1]
	max2 = lst[0]
	print(max(val, max1 * max2 + max1 - max2))


def solve():
	n = int(input())
	l = list(map(int, input().split(' ')))
	l.sort()
	max1 = l[n - 1]
	max2 = l[n - 2]
	maxop1 = max1 * max2 + (max1 - max2)
	maxop2 = l[1] * l[0] + (l[1] - l[0])
	print(max(maxop1, maxop2))
t = int(input())
while t != 0:
	solve()
	t -= 1


t = int(input())
while t != 0:
	n = int(input())
	l = list(map(int, input().split(' ')))
	l.sort()
	a1 = l[n - 1]
	b1 = l[n - 2]
	a2 = l[1]
	b2 = l[0]
	maxx = max(a1 * b1 + a1 - b1, a2 * b2 + a2 - b2)
	print(maxx)
	t -= 1


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


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


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	arr.sort()
	a = arr[0]
	b = arr[1]
	c = arr[-1]
	d = arr[-2]
	ans1 = a * b + max(a - b, b - a)
	ans2 = c * d + max(c - d, d - c)
	print(max(ans1, ans2))


t = int(input())
for _ in range(t):
	n = int(input())
	l1 = list(map(int, input().split()))
	l1.sort()
	(m1, m2) = (-float('inf'), -float('inf'))
	m1 = l1[0] * l1[1] + (l1[1] - l1[0])
	m2 = l1[-1] * l1[-2] + (l1[-1] - l1[-2])
	print(max(m1, m2))


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	a = max(arr)
	arr.remove(a)
	b = max(arr)
	c = a * b + max(a - b, b - a)
	arr.append(a)
	a = min(arr)
	arr.remove(a)
	b = min(arr)
	d = a * b + max(a - b, b - a)
	print(max(c, d))


try:
	t = int(input())
	while t:
		n = int(input())
		l = list(map(int, input().split()))
		l.sort(reverse=True)
		(a, b) = (l[0], l[1])
		(c, d) = (l[n - 1], l[n - 2])
		exp = max(a * b, c * d) + max(max(a - b, b - a), max(c - d, d - c))
		print(exp)
		t -= 1
except EOFError as e:
	pass


def fun(a):
	a.sort()
	m1 = a[-1] * a[-2] + (a[-1] - a[-2])
	m2 = a[0] * a[1] + (a[1] - a[0])
	return max(m1, m2)
for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	print(fun(l))


try:
	m = int(input())
	for i in range(m):
		n = int(input())
		arr = list(map(int, input().split()))
		arr.sort()
		n = len(arr)
		mx1 = arr[n - 1] * arr[n - 2] + (arr[n - 1] - arr[n - 2])
		mx2 = arr[1] * arr[0] + (arr[1] - arr[0])
		ans = max(mx1, mx2)
		print(ans)
except:
	pass