You are given an array $a$ of $n$ integers. You are allowed to perform the following operation on it as many times as you want (0 or more times):

Choose $2$ indices $i$,$j$ where $1 \le i < j \le n$ and replace $a_k$ for all $i \leq k \leq j$ with $|a_i - a_j|$

Print the maximum sum of all the elements of the final array that you can obtain in such a way.


-----Input-----

The first line contains a single integer $t$ ($1 \le t \le 10^5$) — the number of test cases.

The first line of each test case contains a single integer $n$ ($2 \le n \le 2 \cdot 10^5$) — the length of the array $a$.

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$) — the elements of array $a$.

It's guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.


-----Output-----

For each test case, print the sum of the final array.


-----Examples-----

Input
3
3
1 1 1
2
9 1
3
4 9 5
Output
3
16
18


-----Note-----

In the first test case, it is not possible to achieve a sum $> 3$ by using these operations, therefore the maximum sum is $3$.

In the second test case, it can be shown that the maximum sum achievable is $16$. By using operation $(1,2)$ we transform the array from $[9,1]$ into $[8,8]$, thus the sum of the final array is $16$.

In the third test case, it can be shown that it is not possible to achieve a sum $> 18$ by using these operations, therefore the maximum sum is $18$.

Difficulty: HARD
Tags: Greedy algorithms

Complete search

Constructive algorithms
Skill types: Complete search

Greedy algorithms

Starter code:

Solutions:
import sys
input = sys.stdin.readline

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

def readInt():
	return int(input())

def readInts():
	return map(int, input().split())

def readStr():
	return input().strip()

def solve():
	n = readInt()
	arr = readList()
	V = max(arr)
	if n > 3:
		return n * V
	elif n == 2:
		return max(sum(arr), abs(arr[0] - arr[1]) * 2)
	else:
		return max(sum(arr), 3 * arr[0], 3 * arr[-1], 3 * abs(arr[0] - arr[1]), 3 * abs(arr[1] - arr[-1]))
for _ in range(int(input())):
	print(solve())


T = int(input())
while T:
	T -= 1
	n = int(input())
	a = [int(i) for i in input().split()]
	if n > 3:
		print(n * max(a))
	elif n == 2:
		print(max(sum(a), n * abs(a[0] - a[1])))
	elif n == 3:
		print(max(sum(a), n * a[0], n * a[2], n * abs(a[0] - a[2]), n * abs(a[0] - a[1]), n * abs(a[1] - a[2])))


import os
import math
import collections
import bisect
import functools
import itertools
import heapq

def solve(a, n):
	ans = sum(a)
	if len(a) == 2:
		ans = max(ans, abs(a[1] - a[0]) * 2)
		return ans
	m = max(a)
	if len(a) == 3 and a[0] < a[1] > a[2]:
		return max(ans, (m - a[0]) * 2 + a[2], (m - a[2]) * 2 + a[0], 3 * (m - min(a[0], a[2])), 3 * max(a[0], a[2]))
	return m * n
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	print(solve(a, n))


import math
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	if n == 1:
		print(arr[0])
	elif n == 2:
		(a, b) = (sum(arr), abs(arr[0] - arr[1]) * 2)
		print(max(a, b))
	elif n == 3:
		(a, b, c) = arr
		sm = sum(arr)
		if b > a and b > c:
			nm = max(b - min(a, c), max(a, c))
			print(max(sm, nm * 3))
		elif a >= b and a >= c:
			print(max(sm, 3 * a))
		elif c >= a and c >= b:
			print(max(sm, 3 * c))
		else:
			print(sm)
	else:
		print(n * max(arr))


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	if n == 0:
		print(0)
		continue
	if n == 1:
		print(a[0])
		continue
	if n == 2:
		print(max(a[0] + a[1], abs(a[0] - a[1]) * 2))
		continue
	if n == 3:
		print(max(sum(a), a[0] * n, a[-1] * n, abs(a[0] - a[1]) * n, abs(a[-1] - a[1]) * n))
		continue
	print(max(a) * n)


for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	if n == 2:
		print(max(sum(a), abs(a[0] - a[1]) * 2))
	elif n == 3:
		if a[0] >= a[1] and a[0] >= a[2]:
			print(a[0] * n)
		elif a[2] >= a[1] and a[2] >= a[0]:
			print(a[2] * n)
		else:
			f1 = a[0] * n
			f2 = a[2] * n
			f3 = a[0] + 2 * (a[1] - a[2])
			f4 = a[2] + 2 * (a[1] - a[0])
			f5 = sum(a)
			f6 = (a[1] - a[2]) * 3
			f7 = (a[1] - a[0]) * 3
			print(max(f1, f2, f3, f4, f5, f6, f7))
	else:
		print(max(a) * n)


t = int(input())
for test in range(t):
	n = int(input())
	nums = list(map(int, input().split()))
	if len(nums) > 3:
		print(max(nums) * len(nums))
	elif len(nums) == 2:
		print(max(sum(nums), 2 * abs(nums[0] - nums[1])))
	elif len(nums) == 3:
		a = [sum(nums)]
		a.append(3 * max(nums[0], nums[2], abs(nums[1] - nums[0]), abs(nums[1] - nums[2])))
		print(max(a))


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	ans = sum(l)
	if n == 2:
		ans = max(ans, 2 * abs(l[0] - l[1]))
	elif n == 3:
		lx = [l[0], l[2], abs(l[0] - l[1]), abs(l[0] - l[2]), abs(l[1] - l[2])]
		ans = max(ans, max(lx) * 3)
	else:
		ans = max(ans, max(l) * n)
	print(ans)


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	if n == 2:
		print(max(sum(a), 2 * abs(a[0] - a[1])))
	elif n == 3:
		if a[0] == a[1] == a[2]:
			print(a[0] * 3)
		elif a[0] == max(a) or a[-1] == max(a):
			print(max(a) * 3)
		else:
			x = sum(a)
			y = (a[1] - min(a[0], a[-1])) * 3
			print(max(x, y, max(a[0], a[-1]) * 3))
	else:
		print(max(a) * n)


for _ in range(int(input())):
	n = int(input())
	li = list(map(int, input().split()))
	if n == 2:
		print(max(sum(li), 2 * abs(li[0] - li[1])))
	elif n == 3:
		print(max(sum(li), 3 * li[0], 3 * li[2], 3 * abs(li[0] - li[1]), 3 * abs(li[1] - li[2])))
	else:
		print(max(sum(li), n * max(li)))


import heapq

def simple_max(a):
	return max(a) * len(a)
for _ in range(int(input())):
	input()
	a = list(map(int, input().split()))
	if len(a) == 2:
		print(max(sum(a), 2 * (max(a) - min(a))))
		continue
	if len(a) == 3:
		if max(a) > a[0] and max(a) > a[2]:
			print(max(sum(a), simple_max([a[1] - a[0], a[1] - a[0], a[2]]), simple_max([a[0], a[1] - a[2], a[1] - a[2]]), abs(a[0] - a[2])))
		else:
			print(simple_max(a))
		continue
	if len(a) > 3:
		print(simple_max(a))
		continue


for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	if n > 3:
		print(max(a) * n)
	elif n == 2:
		print(max((sum(a), abs(a[0] - a[1]) * 2)))
	else:
		print(max((sum(a), a[0] * 3, a[2] * 3, abs(a[0] - a[1]) * 3, abs(a[1] - a[2]) * 3)))


t = int(input())
for tes in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	if n == 2:
		print(max(a[0] + a[1], abs(a[1] - a[0]) * 2))
	elif n == 3:
		print(max(a[0] + a[1] + a[2], a[0] * 3, a[2] * 3, max(abs(a[1] - a[0]), abs(a[2] - a[1])) * 3, abs(a[0] - a[1]) * 2 + a[2], abs(a[2] - a[1]) * 2 + a[0]))
	else:
		ans = 0
		for i in range(n):
			ans = max(ans, a[i] * n)
		print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	if n >= 4:
		print(n * max(arr))
		continue
	if n == 2:
		print(max(2 * abs(arr[0] - arr[1]), arr[0] + arr[1]))
		continue
	if n == 3:
		(a1, a2, a3) = tuple(arr)
		print(max(a1 + a2 + a3, 3 * a1, 3 * a3, 3 * abs(a1 - a2), 3 * abs(a2 - a3)))
		continue


t = int(input())
while t > 0:
	n = int(input())
	A = list(map(int, input().split()))
	SUM = sum(A)
	if n > 3:
		print(max(A) * n)
	elif n == 2:
		print(max(sum(A), abs(A[0] - A[1]) * n))
	elif n == 3:
		SUM = max(SUM, A[2] + abs(A[0] - A[1]) * 2)
		SUM = max(SUM, A[0] + abs(A[2] - A[1]) * 2)
		SUM = max(SUM, abs(A[0] - A[2]) * 3)
		SUM = max(SUM, abs(A[0] - A[1]) * 3)
		SUM = max(SUM, abs(A[1] - A[2]) * 3)
		SUM = max(SUM, A[0] * 3)
		SUM = max(SUM, A[2] * 3)
		print(SUM)
	t -= 1


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	if n == 2:
		print(max(sum(l), 2 * abs(l[0] - l[1])))
	elif n == 3:
		a = max(l)
		if l[0] == a or l[2] == a:
			print(n * max(l))
		else:
			print(max(sum(l), 3 * l[0], 3 * l[2], 3 * abs(l[0] - l[1]), 3 * abs(l[1] - l[2])))
	else:
		print(n * max(l))


a = int(input())
for _ in range(a):
	b = int(input())
	l = list(map(int, input().split()))
	ans = sum(l)
	if b == 2:
		ans = max(ans, 2 * abs(l[0] - l[1]))
	elif b == 3:
		ll = [l[0], l[2], abs(l[0] - l[1]), abs(l[1] - l[2]), abs(l[0] - l[2])]
		ans = max(ans, max(ll) * 3)
	else:
		ans = max(ans, max(l) * b)
	print(ans)


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


from collections import defaultdict

def solve(aa):
	n = len(aa)
	if n == 1:
		return sum(aa)
	max_val = max(aa)
	if n >= 4:
		return n * max_val
	if n == 2:
		return max(sum(aa), 2 * abs(aa[1] - aa[0]))
	if n == 3:
		if aa[0] == max_val or aa[-1] == max_val:
			return n * max_val
		s1 = sum(aa)
		s2 = 3 * max(abs(aa[0] - aa[1]), aa[2])
		s3 = 3 * max(abs(aa[1] - aa[2]), aa[0])
		s4 = 3 * abs(aa[0] - aa[2])
		return max(s1, s2, s3, s4)
	assert False
n_tests = int(input())
for test_n in range(n_tests):
	n = int(input())
	aa = list(map(int, input().split()))
	assert len(aa) == n
	print(solve(aa))


for tt in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	m = max(a)
	if n >= 4:
		print(n * m)
	elif n == 2:
		print(max(a[0] + a[1], 2 * abs(a[0] - a[1])))
	else:
		print(max(3 * (a[1] - min(a)), sum(a), 3 * a[0], 3 * a[2]))


def ii(num=False):
	i = input().split()
	if num:
		return int(i[0])
	try:
		return list(map(int, i))
	except Exception:
		return i

def gcd(a, b):
	if a == 0:
		return b
	return gcd(b % a, a)
for _ in range(ii(1)):
	(n, a) = (ii(1), ii())
	if n == 2:
		print(max(2 * abs(a[0] - a[1]), a[0] + a[1]))
	elif n == 3:
		print(max(a[0] + a[1] + a[2], 3 * a[0], 3 * a[2], 3 * abs(a[0] - a[1]), 3 * abs(a[1] - a[2])))
	else:
		print(n * max(a))
	pass


for y in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	m = 0
	ind = 0
	for i in range(len(a)):
		if a[i] > m:
			m = a[i]
			ind = i
	if n == 2:
		print(max(2 * abs(a[1] - a[0]), a[1] + a[0]))
	elif n == 3:
		s = sorted(a)
		if m == a[1] and s[2] != s[1]:
			print(max(sum(a), 2 * (a[1] - a[0]) + a[2], 2 * (a[1] - a[2]) + a[0], (a[1] - a[0]) * 3, (a[1] - a[2]) * 3, 3 * a[0], 3 * a[2]))
		else:
			print(m * n)
	else:
		print(m * n)


import math

class Solution:

	def __init__(self) -> None:
		pass

	def read(self):
		self.n = int(input())
		self.arr = list(map(int, input().split()))

	def solve(self):
		if self.n == 2:
			print(max(self.arr[0] + self.arr[1], abs(self.arr[0] - self.arr[1]) * 2))
		elif self.n == 3:
			print(max(self.arr[0] + self.arr[1] + self.arr[2], 3 * self.arr[0], 3 * self.arr[2], 3 * abs(self.arr[0] - self.arr[1]), 3 * abs(self.arr[2] - self.arr[1])))
		else:
			print(max(self.arr) * self.n)
test = int(input())
for _ in range(test):
	testcase = Solution()
	testcase.read()
	testcase.solve()


def N():
	return int(input())

def A():
	return [int(x) for x in input().split()]

def S():
	return input()
for _ in range(N()):
	n = N()
	if 'codeforces' == 28226329:
		print('Tanmay')
	a = A()
	maxi = max(a)
	s1 = sum(a)
	if n == 3:
		print(max(3 * max(abs(a[0] - a[2]), abs(a[1] - a[2]), abs(a[1] - a[0]), a[0], a[2]), s1))
		continue
	if n == 2:
		print(max(s1, (maxi - min(a)) * 2))
		continue
	print(max(s1, n * maxi))


for _ in range(int(input())):
	n = int(input())
	L = list(map(int, input().split()))
	if n > 3:
		print(n * max(L))
	elif n == 1:
		print(L[0])
	elif n == 2:
		a = sum(L)
		diff = abs(L[0] - L[1])
		b = 2 * diff
		print(max(a, b))
	else:
		M = max(L)
		i = L.index(M)
		if i == 0 or i == 2 or L[-1] == M:
			print(M * 3)
		else:
			print(max(sum(L), 3 * abs(L[1] - L[2]), 3 * abs(L[1] - L[0]), L[0] + 2 * abs(L[1] - L[2]), L[2] + 2 * abs(L[1] - L[0]), 3 * L[2], 3 * L[0]))


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	ans = sum(arr)
	for i in range(n):
		if i == 0:
			if n == 2:
				ans = max(ans, 2 * abs(arr[0] - arr[1]))
			else:
				ans = max(ans, arr[i] * n)
		elif i == n - 1:
			if n == 2:
				ans = max(ans, 2 * abs(arr[0] - arr[1]))
			else:
				ans = max(ans, arr[i] * n)
		elif n == 3:
			op1 = abs(arr[0] - arr[i])
			op1 *= n
			op2 = abs(arr[i] - arr[-1])
			op2 *= n
			ans = max(ans, max(op1, op2))
		else:
			ans = max(ans, arr[i] * n)
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	arr = [int(x) for x in input().split()]
	mx = max(arr)
	mi = min(arr)
	s = 0
	for i in range(n):
		s = s + arr[i]
	res = s
	val = 0
	if n == 2:
		res = max(2 * (mx - mi), res)
	elif n == 3:
		q = arr[0] * 3
		w = arr[2] * 3
		e = abs(arr[1] - arr[0]) * 3
		r = abs(arr[1] - arr[2]) * 3
		res = max(res, q, w, e, r)
	elif n > 3:
		res = max(res, mx * n)
	print(res)


from copy import copy

def operation(arr, i, j):
	x = abs(arr[i] - arr[j])
	for k in range(i, j + 1):
		arr[k] = x
	return arr

def solve(n, arr):
	if n >= 4:
		return max(arr) * n
	ans0 = sum(arr)
	if n == 2:
		ans1 = sum(arr)
		arr = operation(arr, 0, 1)
		ans2 = sum(arr)
		return max([ans1, ans2, ans0])
	if n == 3:
		if arr[0] == max(arr) or arr[2] == max(arr):
			return max(arr) * n
		arr2 = copy(arr)
		arr = operation(arr, 0, 1)
		ans1 = max(arr) * n
		arr2 = operation(arr2, 1, 2)
		ans2 = max(arr2) * n
		return max([ans0, ans1, ans2])

def run(i):
	n = int(input())
	arr = [int(x) for x in input().split()]
	ans = solve(n, arr)
	print(ans)
for i in range(int(input())):
	run(i)