Score of a Subsequence

Interview

Time limit2sMemory limit512 MB

Summary

Find the maximum over all contiguous subarrays of the weighted sum where the k-th element from the subarray start contributes k times its value.

Level: Medium5 of 10
Topics: Dynamic programming, Array, Greedy, Prefix sum
Solved: No attempts yet

Problem

The score of a sequence $s = s_1, s_2, \dots, s_n$ is $\sum_{i=1}^{n} i \times s_i$ .

A contiguous subsequence is a sequence of its own, so the weights $1, 2, 3, \dots$ count again from its first term. The score of the contiguous subsequence $s_l, s_{l+1}, \dots, s_r$ is $\sum_{i=l}^{r} (i - l + 1) \times s_i$ .

Write a program that finds the largest score among the contiguous subsequences of $s$ . A subsequence of length 0 can be chosen, and its score is 0.

Input

The first line contains $n$ ( $1 \le n \le 200\,000$ ).

The second line contains $s_1, s_2, \dots, s_n$ . ( $|s_i| \le 10^7$ )

Output

Print the largest score among the contiguous subsequences of $s$ on the first line.

Examples3

Example 1
Input
```
6
5 -1000 1 -3 7 -8
```
Expected output
```
16
```
Example 2
Input
```
5
1000 1000 1001 1000 1000
```
Expected output
```
15003
```
Example 3
Input
```
3
-60 -70 -80
```
Expected output
```
0
```