# Sum this up solution codechef

## Sum this up solution codechef

You are given an array AA with NN positive elements A1,A2,,ANA1,A2,…,AN. You are also given a function SS on any array CC with length NN defined as follow:

S(C)S(C) = i=1N(Ci1+Ci+12Ci)∑i=1N(Ci−1+Ci+12−Ci)

Note that conventionally, we define all elements outside the range of the array to have value 00. In this context, C0=CN+1=0C0=CN+1=0.

Consider the following process:

• Choose a permutation PP of values from 11 to NN uniformly randomly.
• Let BB be the array of NN elements B1,B2,,BNB1,B2,…,BN, where Bi=APiBi=APi.

Define VV as the expected value of |S(B)||S(B)|. Find V⌊V⌋.

Note :

• |X||X| denotes absolute value of XX
• X⌊X⌋ is the greatest integer that does not exceed XX.

### Input Format

• The first line of the input contains an integer TT – the number of test cases. The test cases then follow.
• The first line of each test case contains an integer NN – the size of array.
• The second line of each test case contains NN integers A1,A2,,ANA1,A2,…,AN – the elements of the array.

### Output Format

For each testcase, output V⌊V⌋ in a new line.

### Constraints

• 1T101≤T≤10
• 1N21051≤N≤2⋅105
• 1Ai21051≤Ai≤2⋅105

### Sample Input 1

2
2
1 1
3
8 2 2


### Sample Output 1

1
4


### Explanation

• Test case 22:
• With P=[1,2,3]P=[1,2,3] or P=[1,3,2]P=[1,3,2], we obtain B=[8,2,2]B=[8,2,2], which has |S(B)|=|(0+228)+(8+222)+(2+022)|=5|S(B)|=|(0+22−8)+(8+22−2)+(2+02−2)|=5.
• With P=[2,1,3]P=[2,1,3] or P=[3,1,2]P=[3,1,2], we obtain B=[2,8,2]B=[2,8,2], which has |S(B)|=|(0+822)+(2+228)+(8+022)|=2|S(B)|=|(0+82−2)+(2+22−8)+(8+02−2)|=2.
• With P=[2,3,1]P=[2,3,1] or P=[3,2,1]P=[3,2,1], we obtain B=[2,2,8]B=[2,2,8], which has |S(B)|=|(0+222)+(2+822)+(2+028)|=5|S(B)|=|(0+22−2)+(2+82−2)+(2+02−8)|=5.

Therefore V=5+5+2+2+5+56=4V=5+5+2+2+5+56=4. We output V=4