WPC5E - Galaxy distances

no tags 

Each galaxy 'i' in the universe is assigned a unique position in the universe given by A(i), for the ith galaxy. It is known that the distance between 2 galaxies is given as Dist (i,j) = ( |i^2 - j^2| + |A(i)^2 - A(j)^2| ).

The events are held in a host galaxy, and every other galaxy has to travel to that galaxy to participate. For this, of course, the organizers have to pay the galaxy for their transportation, lodging and daily expenses. The organizers wonder, what could be the maximum transportation expenses that they have to pay?

Help them by finding MAX(Dist (i,j)).

Input:

First line contains a single integer T, denoting the number of Test Cases.

Each Test Case contains 2 lines. 1st line containing a single number ’n’ denoting the number of galaxies (numbered 1 to n).

2nd line contains ’n’ space separated integers signifying A(i) for 1<=i<=n.

 

Warning: Fast IO may be needed in some languages.

 

Output:

T lines, each containing an Integer, the answer to the corresponding test case.

 

Constraints:

1 <= T <= 10

2 <= n <= 10^5

1 <= A(i) <= 10^9

 

Time Limit: 2 seconds

 

Example:

 

Input:

1

2

4 3

 

Output:

10

 

Explanation: Dist(i,j) is maximum for i=1, j=2.

 

The events are held in a host galaxy, and every other galaxy has to travel to that galaxy to participate. For this, of course, the organizers have to pay the galaxy for their transportation, lodging and daily expenses. The organizers wonder, what could be the maximum transporatation expenses that they would have to pay?
Help them find out by finding MAX (Dist (i,j))

 



Added by:triveni
Date:2014-03-29
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:ACA judge IITK, WPC5