You are given a sequence $A_1, A_2, \ldots, A_N$. You may perform the following operation an arbitrary number of times (including zero): choose two adjacent elements of this sequence, i.e. $A_i$, $A_{i+1}$ for some valid $i$, and swap them. However, for each valid $i$, it is not allowed to choose $A_i$ (the element with the index $i$, regardless of its value at any point in time) more than once in total during this process.
Find the maximum of the sum $S = \sum_{i=1}^N A_i \cdot i$.

-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first line of each test case contains a single integer $N$.
- The second line contains $N$ space-separated integers $A_1, A_2, \ldots, A_N$.

-----Output-----
For each test case, print a single line containing one integer ― the maximum possible value of $S$.

-----Constraints-----
- $1 \le T \le 1,000$
- $1 \le N \le 10^5$
- $1 \le A_i \le 10^9$ for each valid $i$
- the sum of $N$ over all test cases does not exceed $10^6$

-----Subtasks-----
Subtask #1 (50 points):
- $N \le 20$
- the sum of $N$ over all test cases does not exceed $200$
Subtask #2 (50 points): original constraints

-----Example Input-----
2
4
2 1 4 3
4
7 6 3 2

-----Example Output-----
30
39

-----Explanation-----
Example case 1: Swap the first and second element of the initial sequence. Then, swap the third and fourth element of the resulting sequence. The final sequence $A$ is $(1, 2, 3, 4)$.
Example case 2: Swap the second and third element to make the sequence $(7, 3, 6, 2)$.

Difficulty: HARD
Tags: Dynamic programming
Skill types: Dynamic programming

Starter code:

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


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


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


def find_max_sum(arr):
	incl = 0
	excl = 0
	for i in arr:
		new_excl = excl if excl > incl else incl
		incl = excl + i
		excl = new_excl
	return excl if excl > incl else incl
for T in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	S = A[0]
	D = A.copy()[1:]
	for i in range(1, N):
		D[i - 1] = A[i - 1] - A[i]
		S += A[i] * (i + 1)
	print(S + find_max_sum(D))


test = int(input())
while test:
	n = int(input())
	arr = [int(x) for x in input().split()]
	if n == 1:
		ans = arr[0]
	elif n == 2:
		t1 = arr[0] + arr[1] * 2
		t2 = arr[0] * 2 + arr[1]
		if t1 > t2:
			ans = t1
		else:
			ans = t2
	else:
		ans = 0
		t = []
		proxy_arr = [1] * n
		for i in range(n - 1):
			ans += arr[i] * (i + 1)
			t.append(arr[i] - arr[i + 1])
		ans += arr[n - 1] * n
		incl = t[0]
		excl = 0
		for i in range(1, n - 1):
			new_excl = max(incl, excl)
			incl = excl + t[i]
			excl = new_excl
		if incl > excl:
			ans += incl
		else:
			ans += excl
	test -= 1
	print(ans)


def esum(arr):
	incl = 0
	excl = 0
	for i in arr:
		new_excl = excl if excl > incl else incl
		incl = excl + i
		excl = new_excl
	return excl if excl > incl else incl
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	k = 0
	for i in range(n):
		k += (i + 1) * l[i]
	l2 = []
	for i in range(n - 1):
		l2.append(l[i] - l[i + 1])
	print(k + esum(l2))


t = int(input())
for T in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	ans = [0] * (n + 1)
	ans[n - 1] = n * a[n - 1]
	for i in range(n - 2, -1, -1):
		v1 = ans[i + 1] + (i + 1) * a[i]
		v2 = ans[i + 2] + (i + 2) * a[i] + (i + 1) * a[i + 1]
		ans[i] = max(v1, v2)
	print(ans[0])


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


from sys import stdin
import resource
import sys
resource.setrlimit(resource.RLIMIT_STACK, [268435456, resource.RLIM_INFINITY])
sys.setrecursionlimit(1048576)

def brute(mydict, garr, index):
	if index >= len(garr):
		return 0
	if index in mydict:
		return mydict[index]
	first = garr[index] + brute(mydict, garr, index + 2)
	second = brute(mydict, garr, index + 1)
	mydict[index] = max(first, second)
	return mydict[index]

def get_gain(arr):
	garr = []
	for i in range(1, len(arr)):
		final = arr[i - 1] * (i + 1) + arr[i] * i
		prev = arr[i - 1] * i + arr[i] * (i + 1)
		garr.append(final - prev)
	return garr

def get_value(arr):
	val = 0
	for i in range(1, len(arr) + 1):
		val += arr[i - 1] * i
	return val
t = int(stdin.readline().strip())
for _ in range(t):
	n = int(stdin.readline().strip())
	arr = list(map(int, stdin.readline().split()))
	garr = get_gain(arr)
	mydict = dict()
	gain = brute(mydict, garr, 0)
	print(gain + get_value(arr))


import sys
sys.setrecursionlimit(1000000)

def f(p, i, l, N):
	if i == N - 2 or i == N - 3:
		return p[i]
	elif i == N - 4:
		return p[N - 2] + p[i]
	elif l[i] >= 0:
		return l[i]
	else:
		l[i] = max(f(p, i + 2, l, N) + p[i], f(p, i + 3, l, N) + p[i])
		return l[i]
T = int(input())
for x in range(T):
	N = int(input())
	A = [int(n) for n in input().split()]
	neg = list()
	if N == 1:
		print(A[0])
	elif N == 2:
		s1 = A[0] + 2 * A[1]
		s2 = A[1] + 2 * A[0]
		print(max(s1, s2))
	elif N == 3:
		p1 = A[0] - A[1]
		p2 = A[1] - A[2]
		if p1 < 0:
			p1 = 0
		if p2 < 0:
			p2 = 0
		maxp = max(p1, p2)
		base = A[0] + 2 * A[1] + 3 * A[2] + maxp
		print(base)
	else:
		if A[0] < 0:
			neg.append(0)
		base = A[0]
		p = []
		for i in range(1, N):
			base += (i + 1) * A[i]
			if A[i - 1] < A[i]:
				p.append(0)
				neg.append(i)
				continue
			p.append(A[i - 1] - A[i])
		l = dict()
		for i in range(N - 1):
			l[i] = -1
		add = max(f(p, 0, l, N), f(p, 1, l, N))
		print(base + add)


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


tcase = int(input())
while tcase > 0:
	tcase -= 1
	n = int(input())
	l = list(map(int, input().split()))
	dp = dict()
	(dp[0], dp[1]) = (0, l[0])
	for i in range(2, n + 1):
		dp[i] = max(dp[i - 2] + l[i - 1] * (i - 1) + l[i - 2] * i, dp[i - 1] + l[i - 1] * i)
	print(dp[n])


from sys import stdin
from math import sqrt, floor, ceil, gcd, factorial
from collections import Counter
import sys
sys.setrecursionlimit(1000000)

def gti():
	return map(int, stdin.readline().split())

def gli():
	return list(gti())

def gi():
	return int(stdin.readline())

def gs():
	return stdin.readline()

def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		(g, y, x) = egcd(b % a, a)
		return (g, x - b // a * y, y)

def modinv(a, m):
	(g, x, y) = egcd(a, m)
	return x % m

def prime_num_sieve(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	Pr = []
	for j in range(2, len(prime)):
		if prime[j]:
			Pr.append(j)
	return Pr

def primeFactors(n):
	prime_fac = []
	if n % 2 == 0:
		prime_fac.append(2)
	while n % 2 == 0:
		n = n / 2
	for i in range(3, int(sqrt(n)) + 1, 2):
		flag = 0
		while n % i == 0:
			n = n / i
			flag = 1
		if flag == 1:
			prime_fac.append(i)
	if n > 2:
		prime_fac.append(n)
	return prime_fac

def binary_search(lis, l, r, elem):
	while l <= r:
		mid = l + (r - l) // 2
		if lis[mid] == elem:
			return mid
		elif lis[mid] > elem:
			r = mid - 1
		else:
			l = mid + 1
	return -1

def prefix_su(lis):
	ret = [0]
	for i in lis:
		ret.append(ret[-1] + i)
	return ret
t = gi()
for _ in range(t):
	n = gi()
	arr = gli()
	dp = [-1] * (n + 1)
	dp[0] = 0
	dp[1] = arr[0]
	for i in range(2, n + 1):
		dp[i] = dp[i - 1] + arr[i - 1] * i
		dp[i] = max(dp[i], dp[i - 2] + arr[i - 1] * (i - 1) + arr[i - 2] * i)
	print(dp[n])


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


t = int(input())
for _ in range(t):
	n = int(input())
	l = [int(p) for p in input().split()]
	d = set
	ans = 0
	li = [0] * (n + 1)
	li[0] = 0
	li[1] = l[0]
	for i in range(2, n + 1):
		li[i] = max(li[i - 1] + l[i - 1] * i, li[i - 2] + l[i - 2] * i + l[i - 1] * (i - 1))
	print(li[-1])


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


try:
	for _ in range(int(input())):
		N = int(input())
		arr = list(map(int, input().split()))
		ms = [0 for k in range(N + 1)]
		ms[1] = arr[0]
		for i in range(2, N + 1):
			ms[i] = max(ms[i - 2] + arr[i - 2] * i + arr[i - 1] * (i - 1), ms[i - 1] + arr[i - 1] * i)
		print(ms[-1])
except:
	pass


import random

def calc_sum(arr):
	sum_ = 0
	for a in range(1, len(arr) + 1):
		sum_ += arr[a - 1] * a
	return sum_

class Memo:

	def __init__(self, fn):
		self.fn = fn
		self.memory = {}

	def __call__(self, *args):
		if args[1] not in self.memory:
			self.memory[args[1]] = self.fn(*args)
		return self.memory[args[1]]

def solve(arr, index):
	if index >= len(arr) - 1:
		print(arr, calc_sum(arr))
		return calc_sum(arr)
	first = 0
	if arr[index] > arr[index + 1]:
		(arr[index], arr[index + 1]) = (arr[index + 1], arr[index])
		first = solve(arr, index + 2)
	else:
		(arr[index], arr[index + 1]) = (arr[index + 1], arr[index])
	(arr[index], arr[index + 1]) = (arr[index + 1], arr[index])
	second = solve(arr, index + 1)
	return max(first, second)

def solve_dp(arr, n):
	dp = [0 for i in range(n + 1)]
	dp[1] = arr[0]
	for i in range(2, n + 1):
		dp[i] = max(dp[i - 2] + arr[i - 2] * i + arr[i - 1] * (i - 1), dp[i - 1] + arr[i - 1] * i)
	return dp[n]

def solve1(arr, n):
	flag = [True] * n
	swap_values = {}
	for i in range(n - 1):
		if arr[i] > arr[i + 1]:
			swap_values[i] = (i + 2) * arr[i]
	arr_sort = list(reversed([i[0] for i in sorted(swap_values.items(), key=lambda x: x[1])]))
	for i in arr_sort:
		if i < n - 1:
			if flag[i] != False and flag[i + 1] != False:
				(arr[i], arr[i + 1]) = (arr[i + 1], arr[i])
				flag[i] = False
				flag[i + 1] = False
	return calc_sum(arr)

def main():
	t = int(input())
	for a in range(t):
		n = int(input())
		arr = list(map(int, input().split()))
		print(solve_dp(arr, len(arr)))
main()


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


def find_max_sum(arr):
	incl = 0
	excl = 0
	for i in arr:
		new_excl = excl if excl > incl else incl
		incl = excl + i
		excl = new_excl
	return excl if excl > incl else incl
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	dp = []
	s = a[-1] * n
	for x in range(n - 1):
		s += (x + 1) * a[x]
		dp.append(a[x] - a[x + 1])
	print(max(find_max_sum(dp) + s, s))


def function(n, arr, i, dp):
	if i >= n - 1:
		sum = 0
		pointer = 1
		s = ''
		for k in arr:
			sum += k * pointer
			pointer += 1
			s += str(k)
		dp[s] = sum
		return sum
	s = ''
	for l in arr:
		s += str(l)
	if dp.get(s, -1) == -1:
		val = function(n, arr, i + 1, dp)
	else:
		val = dp[s]
	for j in range(i, n - 1):
		(arr[j], arr[j + 1]) = (arr[j + 1], arr[j])
		s = ''
		for l in arr:
			s += str(l)
		if dp.get(s, -1) == -1:
			val1 = function(n, arr, j + 2, dp)
		else:
			val1 = dp[s]
		val = val if val > val1 else val1
		(arr[j], arr[j + 1]) = (arr[j + 1], arr[j])
	return val
times = int(input())
while times > 0:
	times -= 1
	n = int(input())
	arr = [int(i) for i in input().split()]
	dp = {}
	print(function(n, arr, 0, dp))


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	if n == 1:
		print(a[0])
		continue
	elif n == 2:
		print(max(a[0] + a[1] * 2, a[0] * 2 + a[1]))
	else:
		dp = [0] * (n + 1)
		dp[0] = a[0]
		dp[1] = max(a[0] + a[1] * 2, a[0] * 2 + a[1])
		for i in range(2, n):
			m1 = dp[i - 2] + a[i - 1] * i + a[i] * (i + 1)
			m2 = dp[i - 2] + a[i] * i + a[i - 1] * (i + 1)
			m3 = dp[i - 1] + a[i] * (i + 1)
			dp[i] = max(m1, m2, m3)
		print(dp[n - 1])


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

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

def nu():
	return int(input())

def solve():
	t = nu()
	for _ in range(t):
		n = nu()
		l = li()
		dp = [0] * (n + 1)
		dp[1] = l[0]
		for i in range(2, n + 1):
			dp[i] = max(dp[i - 1] + l[i - 1] * i, dp[i - 2] + i * l[i - 2] + (i - 1) * l[i - 1])
		print(dp[n])
solve()


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


t = int(input())
while t > 0:
	n = int(input())
	arr = [int(x) for x in input().split()]
	dp = [0 for i in range(n + 1)]
	dp[1] = arr[0]
	for i in range(1, n):
		dp[i + 1] = max(dp[i] + (i + 1) * arr[i], dp[i - 1] + i * arr[i] + (i + 1) * arr[i - 1])
	print(dp[n])
	t -= 1


t = int(input())
while t:
	t = t - 1
	n = int(input())
	li = list(map(int, input().split()))
	li.insert(0, 0)
	dp = [0] * (n + 1)
	dp[1] = li[1]
	for i in range(2, n + 1):
		x = dp[i - 1] + i * li[i]
		y = dp[i - 2] + (i - 1) * li[i] + i * li[i - 1]
		if x > y:
			dp[i] = x
		else:
			dp[i] = y
	print(dp[n])


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


t = int(input())
while t != 0:
	n = int(input())
	a = list(map(int, input().split()))
	u = [0] * (len(a) + 1)
	s = [0] * (len(a) + 1)
	u[1] = a[0]
	for i in range(1, len(a)):
		u[i + 1] = max(u[i], s[i]) + a[i] * (i + 1)
		s[i + 1] = max(u[i - 1], s[i - 1]) + a[i] * i + a[i - 1] * (i + 1)
	print(max(u[n], s[n]))
	t -= 1


test = int(input())
for _ in range(test):
	n = int(input())
	arr = list(map(int, input().split()))
	dp = [0] * (n + 1)
	sumval = 0
	dp[n - 1] = arr[n - 1] * n
	for i in range(n - 2, -1, -1):
		dp[i] = max(arr[i] * (i + 1) + dp[i + 1], arr[i] * (i + 2) + arr[i + 1] * (i + 1) + dp[i + 2])
	print(dp[0])


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


n = int(input())
for e in range(0, n):
	k = int(input())
	l = list(map(int, input().split(' ')))
	swap = [0] * k
	notswap = [0] * k
	swap[0] = l[1]
	notswap[0] = l[0]
	for i in range(1, k):
		if i != k - 1:
			swap[i] = notswap[i - 1] + l[i + 1] * (i + 1)
		notswap[i] = max(notswap[i - 1] + l[i] * (i + 1), swap[i - 1] + l[i - 1] * (i + 1))
	print(max(swap[k - 1], notswap[k - 1]))


import sys
sys.setrecursionlimit(100000)

def solve(idx):
	if idx > n:
		return 0
	if dp[idx] != -1:
		return dp[idx]
	if idx == n:
		return n * a[n]
	else:
		dp[idx] = max(a[idx] * (idx + 1) + a[idx + 1] * idx + solve(idx + 2), a[idx] * idx + solve(idx + 1))
		return dp[idx]
for T in range(int(input())):
	n = int(input())
	a = [0]
	a += [int(x) for x in input().split()]
	dp = [-1] * (n + 1)
	solve(1)
	print(max(dp))


t = int(input())
for _ in range(t):
	n = int(input())
	arr = [int(x) for x in input().split()]
	dp = {}
	dp[int(0)] = int(0)
	dp[1] = arr[0]
	for i in range(2, n + 1):
		dp[i] = max(dp[i - 1] + arr[i - 1] * i, dp[i - 2] + arr[i - 2] * i + (i - 1) * arr[i - 1])
	print(dp[n])


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	if n == 1:
		print(a[0])
	else:
		swapMax = [0] * n
		noSwapMax = [0] * n
		swapMax[0] = a[0]
		noSwapMax[0] = a[0]
		noSwapMax[1] = a[0] + 2 * a[1]
		swapMax[1] = a[1] + 2 * a[0]
		for j in range(2, n):
			noSwapMax[j] = max(noSwapMax[j - 1], swapMax[j - 1]) + (j + 1) * a[j]
			swapMax[j] = max(swapMax[j - 2], noSwapMax[j - 2]) + j * a[j] + (j + 1) * a[j - 1]
		print(max(swapMax[n - 1], noSwapMax[n - 1]))


from sys import stdin

def dp(li, i):
	for j in range(2, i):
		l2[j] = max(l2[j - 1] + li[j] * (j + 1), l2[j - 2] + li[j - 1] * (j + 1) + li[j] * j)
	return l2[-1]
n = stdin.readline()
n = int(n)
for _ in range(n):
	t = int(stdin.readline())
	amt = 0
	li = [int(e) for e in stdin.readline().split()]
	if t > 1:
		l2 = [0] * t
		l2[0] = li[0]
		l2[1] = max(li[0], li[1]) * 2 + min(li[0], li[1])
		amt = dp(li, t)
		print(str(amt))
	else:
		print(li[-1])


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


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


test = int(input())
while test:
	n = int(input())
	arr = [int(x) for x in input().split()]
	dynamic_p = [0] * (n + 1)
	dynamic_p[1] = arr[0]
	for i in range(2, n + 1):
		dynamic_p[i] = max(dynamic_p[i - 2] + i * arr[i - 2] + (i - 1) * arr[i - 1], dynamic_p[i - 1] + arr[i - 1] * i)
	test -= 1
	print(dynamic_p[n])


for _ in range(int(input())):
	last = int(input())
	nl = [int(x) for x in input().split()]
	ansl = [0] * (last + 1)
	ansl[last - 1] = last * nl[last - 1]
	for i in range(last - 2, -1, -1):
		ansl[i] = max(ansl[i + 1] + (i + 1) * nl[i], ansl[i + 2] + (i + 2) * nl[i] + (i + 1) * nl[i + 1])
	print(ansl[0])


test = int(input())
while test:
	n = int(input())
	x = list(map(int, input().split()))
	x.insert(0, 0)
	maxV = []
	maxV.append(0)
	maxV.append(x[1])
	for i in range(2, len(x)):
		z = maxV[i - 1] + x[i] * i
		w = maxV[i - 2] + x[i] * (i - 1) + x[i - 1] * i
		r = max(z, w)
		maxV.append(r)
	print(maxV[len(maxV) - 1])
	test = test - 1


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().rstrip().split()))
	dp = [0] * (n + 1)
	for i in range(n + 1):
		if i == 0:
			dp[i] = 0
		elif i == 1:
			dp[i] = l[i - 1]
		else:
			dp[i] = max(dp[i - 1] + l[i - 1] * i, dp[i - 2] + l[i - 1] * (i - 1) + l[i - 2] * i)
	print(dp[n])


for i in range(int(input())):
	n = int(input())
	A = []
	A = [int(x) for x in input().split()]
	dp = []
	dp.append(A[0])
	for j in range(1, n):
		dp.append(dp[j - 1] + A[j] * (j + 1))
		if j < 2:
			dp[j] = max(dp[j], A[j] * j + A[j - 1] * (j + 1))
			if dp[j] == A[j] * j + A[j - 1] * (j + 1):
				dp[0] = A[1]
		else:
			dp[j] = max(dp[j], A[j - 2] + A[j] * j + A[j - 1] * (j + 1), dp[j - 2] + A[j] * j + A[j - 1] * (j + 1))
	print(max(dp))


dp = [0] * 100001
for _ in range(int(input())):
	n = int(input())
	arr = []
	arr.append(0)
	q = [int(s) for s in input().split()]
	for i in q:
		arr.append(i)
	dp[0] = 0
	dp[1] = arr[1]
	for i in range(2, n + 1):
		dp[i] = dp[i - 1] + arr[i] * i
		dp[i] = max(dp[i], dp[i - 2] + arr[i] * (i - 1) + arr[i - 1] * i)
	print(dp[n])


t = int(input())
while t > 0:
	n = int(input())
	data = list(map(int, input().split()))
	data.insert(0, 0)
	arr = [0] * (n + 1)
	arr[1] = data[1]
	for i in range(2, n + 1):
		arr[i] = max(arr[i - 1] + data[i] * i, arr[i - 2] + data[i - 1] * i + data[i] * (i - 1))
	print(arr[n])
	t -= 1


t = int(input())
while t != 0:
	n = int(input())
	num = list(input().split())
	dp = []
	dp.append(0)
	dp.append(int(num[0]))
	for i in range(1, len(num)):
		dp.append(max(dp[i - 1] + int(num[i]) * i + int(num[i - 1]) * (i + 1), dp[i] + int(num[i]) * (i + 1)))
	print(dp[-1])
	t = t - 1


def find_max_sum(arr):
	incl = 0
	excl = 0
	for num in arr:
		new_excl = max(incl, excl)
		incl = excl + num
		excl = new_excl
	return max(incl, excl)
T = int(input())
output = [0] * T
for t in range(T):
	n = int(input())
	a = list(map(int, input().split()))
	diff = [a[i] - a[i + 1] for i in range(n - 1)]
	ans = a[0]
	for i in range(1, n):
		ans += (i + 1) * a[i]
	output[t] = str(ans + find_max_sum(diff))
print('\n'.join(output))


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


for I in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	dp = [0] * (n + 1)
	for i in range(n, -1, -1):
		if i == n:
			dp[i] = 0
		else:
			dp[i] = a[i] * (i + 1) + dp[i + 1]
			if i + 1 < n:
				dp[i] = max(dp[i], a[i + 1] * (i + 1) + a[i] * (i + 2) + dp[i + 2])
	print(dp[0])


T = int(input())
for t in range(T):
	n = int(input())
	A = [int(i) for i in input().split()]
	A.append(0)
	dp = [0] * (n + 1)
	for i in range(n, -1, -1):
		if i == n:
			dp[i] = 0
		else:
			dp[i] = A[i] * (i + 1) + dp[i + 1]
			if i + 1 < n:
				dp[i] = max(dp[i], A[i + 1] * (i + 1) + A[i] * (i + 2) + dp[i + 2])
	print(dp[0])


def fun(i, l):
	if i >= n:
		return 0
	if i + 1 >= n:
		return l[i] * (i + 1) + fun(i + 1, l)
	return max(l[i] * (i + 2) + l[i + 1] * (i + 1) + fun(i + 2, l), l[i] * (i + 1) + fun(i + 1, l))
t = int(input())
while t > 0:
	n = int(input())
	l = list(map(int, input().split()))
	dp = [0] * (n + 1)
	i = n - 1
	while i >= 0:
		if i + 1 >= n:
			dp[i] = l[i] * (i + 1)
		else:
			dp[i] = max(l[i] * (i + 2) + l[i + 1] * (i + 1) + dp[i + 2], l[i] * (i + 1) + dp[i + 1])
		i -= 1
	i = 0
	print(dp[0])
	t -= 1


import math
from sys import stdin, stdout
from bisect import bisect_left, bisect_right
from copy import deepcopy

def isprime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	i = 5
	while i * i <= n:
		if n % i == 0 or n % (i + 2) == 0:
			return False
		i = i + 6
	return True

def freq(l):
	f = {}
	for i in l:
		if i in f:
			f[i] += 1
		else:
			f[i] = 1
	return f
MAX = pow(10, 5)
inp = lambda : int(stdin.readline())
sip = lambda : stdin.readline()
mulip = lambda : map(int, stdin.readline().split())
lst = lambda : list(map(int, stdin.readline().split()))
slst = lambda : list(sip())
for _ in range(inp()):
	N = inp()
	A = lst()
	(natural, swapped) = ([A[0]], [A[0]])
	for i in range(1, N):
		natural.append(max(natural[i - 1], swapped[i - 1]) + A[i] * (i + 1))
		swapped.append(max(natural[i - 1] + A[i] * (i + 1), natural[i - 1] - A[i - 1] * i + A[i] * i + A[i - 1] * (i + 1)))
	print(max(natural[N - 1], swapped[N - 1]))


def find_max_sum(arr):
	incl = 0
	excl = 0
	for i in arr:
		new_excl = excl if excl > incl else incl
		incl = excl + i
		excl = new_excl
	return excl if excl > incl else incl
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split(' ')))
	z = a[0]
	b = []
	for i in range(1, n):
		z += a[i] * (i + 1)
		b.append(a[i - 1] - a[i])
	s = z + find_max_sum(b)
	print(s)


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


import sys
from collections import defaultdict as dc
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	s = 0
	b = []
	for i in range(n):
		s = s + a[i] * (i + 1)
	p = [0] * n
	q = [0] * n
	p[0] = q[0] = a[0]
	for i in range(1, n):
		p[i] = max(p[i - 1], q[i - 1]) + a[i] * (i + 1)
		q[i] = max(q[i - 1] + a[i] * (i + 1), p[i - 1] - a[i - 1] * i + (a[i] * i + a[i - 1] * (i + 1)))
	print(max(p[-1], q[-1]))


for t in range(int(input())):
	n = int(input())
	arr = [int(a) for a in input().split()]
	Arr = [0]
	for i in range(n):
		Arr.append(arr[i])
	for i in range(2, n + 1):
		Arr[i] = Arr[i - 1] + i * Arr[i]
		k = Arr[i - 2] + (i - 1) * arr[i - 1] + i * arr[i - 2]
		if k > Arr[i]:
			Arr[i] = k
	print(Arr[n])


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