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$