B. Ginger's game
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

There are $$$n$$$ monsters with $$$a_1,a_2,\dots,a_n$$$ HP in game. Before the start of the game, Ginger can set the HP $$$a_i$$$ of each monster to any non-negative integer less than or equal to $$$a_i$$$. When the game starts, Ginger can choose any position $$$i$$$ $$$(1 \le i \le n)$$$, and then Ginger must kill the monsters in the order of $$$i, i - 1, \cdots, 1$$$, and the HP of the attacked monsters must follow the order of non-strict decreasing, Ginger will get $$$\sum_{j = 1} ^ {i} a_j$$$ money.

Find the maximum money.

Input

The first line contains a integer $$$n$$$ $$$(1 \le n \le 2 \times 10 ^ 5)$$$ indicating the number of monsters HP.

The second line contains $$$n$$$ integers $$$a_1,a_2, \dots, a_n$$$ $$$(1 \le a_i \le 10 ^ 9)$$$ indicating the monsters HP.

Output

Print the maximum money.

Example
Input
5
8 5 4 7 2
Output
19
Note

For test case:

Before the start of the game, the monster's HP is set to $$$[4 , 4 , 4 , 7 , 2]$$$.

When the game starts, Ginger chooses position $$$i = 4$$$, Ginger will get $$$7 + 4 + 4 + 4 = 19$$$ money.