The Running Game

A game where you run along a straight line and eat scored objects one after another is popular right now. Kyungkeun, who picks up trends a little late, made one of these games too. It has no name yet.

The game has a multiplier that is applied to the score of every object the character eats. The multiplier is 0 when the game starts. The character starts from a point far to the left and runs to the right, meeting the objects Kyungkeun placed on the line in order. When the character eats an object, the multiplier first increases by 1, and then (score of the eaten object) $\times$ (the increased multiplier) is added to the score the character has collected. When the character does not eat an object, the multiplier resets to 0 and no score is gained. An object's score is not guaranteed to be positive, so a high score requires choosing carefully which objects to eat and which to pass. Once that is decided the character runs on to the right, and it can never go back to the left.

On Kyungkeun's map the character meets $N$ objects in order. Given the scores of the objects in the order they are placed, find the largest score the character can collect.

The first line contains a natural number $N$ ($1 \le N \le 10^6$).

The second line contains $N$ integers separated by spaces, the scores of the objects. They are given in the order the objects are placed on the map, so the character meets them in that order. The absolute value of each integer is at most $10^6$.

Print the largest score the character can collect on the given map. The answer can exceed the range of a 32-bit integer, so use a 64-bit integer type.

In the first example, eating all three objects is best.

• Eating only the third object gives $5 \times 1 = 5$ points.
• Eating the second and the third object gives $(-1) \times 1 + 5 \times 2 = 9$ points.
• Eating all three objects gives $(-1) \times 1 + (-1) \times 2 + 5 \times 3 = 12$ points.