Fluoride Dentist

Time limit3sMemory limit1024 MB

Summary

Given values a_i, Bjorn (the one with a_i=0) may reinsert himself anywhere; maximize the sum of i*a_i.

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

Problem

Björn and $n-1$ other people are standing in line to see the fluoride dentist. Different people find meeting the fluoride dentist scary to different degrees. The people are numbered from $1$ to $n$ , and person $i$ stands in position $i$ in the line. Person $i$ also has a value $a\_i$ , which shows how reluctant the person is to meet the fluoride dentist. Person $i$ 's happiness with their position in the line is $i \cdot a\_i$ . Some people may have a negative $a\_i$ , which means they actually want to meet the fluoride dentist and are therefore sad about having to wait.

Björn is the only person who is completely indifferent to meeting the fluoride dentist, that is, he is the only person with $a\_i = 0$ . He is also very kindhearted, so he decides to leave the line and then re-enter the line at some position so that the total happiness of everyone in the line becomes as large as possible. Write a program that, given the values $a\_i$ for all people, computes the maximum sum of happiness in the line when Björn stands in an optimal position.

Input

The first line contains an integer $n$ , the number of people in the line. The next line contains $n$ integers, where the $i$ th integer is $a\_i$ . $1 \leq n \leq 10^6$ , $-1000 \leq a\_i \leq 1000$ .

Output

Print one line with a single integer: the maximum total happiness in the line.

Examples3

Example 1
Input
```
3
1 0 -2
```
Expected output
```
-3
```
Example 2
Input
```
5
0 -8 1 1 5
```
Expected output
```
24
```
Example 3
Input
```
7
2 -4 5 -3 0 -1 2
```
Expected output
```
7
```