Problem D
Fluortanten

Björn and $n-1$ other children stand in line to meet the "fluortant" (the fluoride administrator, who comes to school to give children fluoride treatments). Different children are more or less scared of the fluortant. The children are numbered from $1$ to $n$, and child $i$ is in position $i$ in the queue. Child $i$ also has associated value $a_ i$, which shows how reluctant the child is to meet the fluortant. The happiness that child $i$ feels of their place in the queue is $i \cdot a_ i$. A child can have negative $a_ i$, which means that they actually want to meet the fluortant and thus are sorry to have to wait.

Björn is the only child who is completely indifferent to meeting the fluortant, that is, he is the only child who has $a_ i = 0$. In addition, he is very kindhearted, so he decides to leave the queue and then enter the queue again somewhere so that the total happiness of everyone in the queue is as great as possible. Write a program that, given the values $a_ i$ for all children, calculates the maximum sum of the happiness in the queue if Björn stands in an optimal place.

Input

The first line contains an integer $n$, the number of children in the queue. On the next line are $n$ integers, where the $i$th number is $a_ i$. $1 \leq n \leq 10^6 $, $-1\, 000 \leq a_ i \leq 1\, 000$.

Output

Print a line with one integer: the maximum total happiness in the queue.

Points

Your solution will be tested on several test case groups. To get points for a group your submission must pass all the test cases in the group.

Explanation of example 1

Björn is last in the queue. The sum of the happiness is then $1 \cdot 1 + 2\cdot (-2) + 3 \cdot 0 = -3$.

If Björn moves to the front of the queue, the sum of the happiness would be $1 \cdot 0 + 2 \cdot 1 + 3 \cdot (-2) = -4$, and in the middle it would be $1 \cdot 1 + 2 \cdot 0 + 3 \cdot (-2) = -5$. Both of these are worse alternatives.

3
1 0 -2

-3

5
0 -8 1 1 5

24

7
2 -4 5 -3 0 -1 2

7