You have been given an array of N coins. As per the rules the following tasks can be performed:-

• Swap adjacent coins.

• Once a pair of coins is swapped, they cannot be swapped with any other coin.

Given the initial position of coins on the board represented by array A. calculate the maximum power of array. Power of Array is: Σ A[i]*i

Find the maximum possible value of Power Of Array that can be achieved with the given array and the mentioned rules.

Note: Indexing of array A starts from 1.

Input Specification:

input1: An integer value N denoting the number of coins.

input2: An integer array A denoting the coins.

Output Specification:

Return an integer value denoting the maximum power of given array.

Example:

input1:4

input2: (2,4,5,3)

Output: 39

Explanation:

Power of array of (2, 4, 5, 3) is (2*1+ 4*2+5*3 +3*4) = 37. The only way to get maximum power of array is by swapping A[3] with A[4].

The only way to get maximum power of array is by swapping A[3] with A[4]. On doing so, the array becomes (2, 4, 3, 5) and the power of array is (2*1 +4*2+3*3+5*4) = 39.

Therefore, 39 is returned as the output.