Chuchu has got an array \(A\) of \(n\) intergers and he want to maximize the power of the array. Power of an array is defined as, 

• \(Power(A) = \sum_{i=1}^{n} i \cdot A_i\)

In order to maximize the power, he is allowed to do following operation at most once,

• Pick any element from the given array and insert it at any other position.(While inserting, some elements of array get shifted accordingly). 

Note: Given array \(A\) is 1-indexed.

Input:

• First line contains a integer \(n\), denoting size of array.
• Second line contains  \(n \) space separated integers, each denoting \(A_i\).

Output:

Print the maximum power of array Chuchu can obtain after performing given operation at most once.

Constraints:

• \(1 \le n\le 200000\)
• \(0 \le \lvert A_i \rvert \le 10^6\)