Cheap Thrills

All submissions for this problem are available.
Vinod is bored, so he decided to play a quick game. He has a sequence 'S' consisting of N integers and an empty array A.
In each step Vinod removes either first or last number of sequence S and adds it at the end of the array A. This game continues till there are no more numbers left in S. In the end of the game, array A has N numbers.
Now maximum of 2^{n1} permutations of array A are possible depending upon how numbers are removed from the sequence S.
Cost of array A is defined as S[1]+S[2]+.....+S[N1]+S[N]. Where
S[1]=A[1]
S[2]=A[2]*(A[1]+1)
S[i]=A[i]*(A[i1]+1)*(A[i2]+2) for 3<=i<=N
Now out of all possible permutations of A, Vinod wants to create array A in such a way that its cost is minimized. Help him find the least cost of array A out of all possible cases.
Input
Input consists of single integer T representing numbers of games Vinod is going to play. Now for each game :
First line contains single integer N denoting size of sequence S.
Second line contains N integers denoting numbers in the sequence S.
Output
For each game, print the least possible cost of array A in new line.
Constraints
 1 <=T<=25
 1 <=N <=10^{3}
 1 <=A[i] <=10^{3}
Example
Input: 6 1 11 2 4 7 3 1 2 2 3 1 4 2 4 1 5 3 8 4 8 4 3 5 Output: 11 39 20 34 125 314
Explanation
For test case 1, we select 11, so answer is 11.
For test case 2, we can select [4,7] or [7,4], and both will give 4+7*(4+1)=7+4*(7+1)=39.
For test case 3, if we select in order [2,2,1], we get 2+2*(2+1)+1*(2+1)*(2+2)=20.
For test case 4, we can select in order [2,4,1], and we get 2+4*(2+1)+1*(4+1)*(2+2)=34.
For test case 5, selecting in order [8,3,1,5] will give least cost=125.
For test case 6, selecting in order [8,4,3,5] will give least cost=314.
Author:  vinod10 
Tags  vinod10 
Date Added:  15102017 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, CLOJ, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions