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: interview

Starter code:

Solutions:
# cook your dish here
# cook your dish here
for _ in range(int(input())):
 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]) 

# cook your dish here
for _ in range(int(input())):
 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]) 

# cook your dish here
# cook your dish here
for t in range(int(input())):
 n = int(input())
 a = list(map(int,input().split()))
 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 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])

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

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


# cook your dish here
#SFRV
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])

# cook your dish here
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:
   ##dekho swap kare ya nahi but prev wala
   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])

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

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])

# cook your dish here
for t in range(int(input())):
 n = int(input())
 a = list(map(int,input().split()))
 dp = [0 for i in range(n+1)]
 
 dp[1] = a[0]
 #print(dp)
 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('Pass {}: {}'.format(i,dp))
 print(dp[n])

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

def function(n,arr,i,dp) :
 if i >= n-1 :
  sum = 0
  pointer = 1
  s = ''
  #print('arr:',arr)
  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 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])