I. Treat To Banta Hai
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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

$$$\sum_{i=1}^{k}$$$ $$$i$$$ $$$\cdot$$$ $$$s_i$$$

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?

Input

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.

Output

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

Examples
Input
6
5 -1000 1 -3 7 -8
Output
16
Input
5
1000 1000 1001 1000 1000
Output
15003
Input
3
-60 -70 -80
Output
0
Note

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.