409825: GYM103800 B Ginger's game
Description
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.
InputThe 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.
OutputPrint the maximum money.
ExampleInput5 8 5 4 7 2Output
19Note
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.