406963: GYM102625 I Treat To Banta Hai

Its high time for juniors, as seniors are getting placed one by one and it time for them to ask for a grand treat.

For giving these treats our senior gets happiness score — an integer (maybe negative) number of points. Value for the $$$i^{th}$$$ treat is multiplied by i and are summed up. So, for $$$k$$$ treats with value $$$s_1$$$, $$$s_2$$$, ..., $$$s_k$$$, the happiness score is

The happiness score is $$$0$$$ if there were no treats were given.

The senior had n juniors asking for a treat and has value $$$s_i$$$ for the $$$i^{th}$$$ of them. He wants to maximize his happiness score and being a competitive programmer he doesn't want to just give it to all of them. He gave himself a problem where he would only give treat to some number of contiguous juniors. More formally, he can cancel any prefix and any suffix of the sequence $$$s_1$$$ , $$$s_2$$$ , ..., $$$s_n$$$. It is allowed to cancel all the treats, or to cancel none of them.

The happiness score is calculated as if there were only non-canceled treats. So, for calculating happiness score he will take summation of the $$$1^{st}$$$ non-canceled one's value multiplied by 1, the $$$2^{nd}$$$ one's value multiplied by 2, and so on, till the last non-canceled junior's treat.

What maximum happiness score can the senior get? He found the problem very challenging so he left it for you to solve. Can you solve it for him?

The first line contains a single integer $$$n$$$ (1 $$$\leq$$$ $$$n$$$ $$$\leq$$$ 2·$$$10^5$$$ ) — the total number of juniors who asked for treat.

The second line contains $$$n$$$ integers $$$s_1$$$ , $$$s_2$$$ , ..., $$$s_n$$$ ( $$$\mid s_i \mid $$$ $$$\leq$$$ $$$10^7$$$ ) — value for corresponding junior.

Print the maximum possible happiness score after all the treats he would possibly give.

6
5 -1000 1 -3 7 -8

16

5
1000 1000 1001 1000 1000

15003

3
-60 -70 -80

0

In the first sample test,our senior should cancel the first two treats, and one last treat. He will be left with juniors with values 1,- 3, 7 what gives him the happiness score= 1·1 + 2·( - 3) + 3·7 = 1 - 6 + 21 = 16.