# [Kattis] Fluortanten

>題目連結:https://open.kattis.com/problems/fluortanten

Björn and $n−1$ other children stand in line to meet the "fluortant" (the fluoride administrator, who comes to school to give children fluoride treatments). Different children are more or less scared of the fluortant. The children are numbered from $1$ to $n$, and child $i$ is in position $i$ in the queue. Child $i$ also has associated value $a_i$, which shows how reluctant the child is to meet the fluortant. The happiness that child $i$ feels of their place in the queue is $i⋅a_i$. A child can have negative $a_i$, which means that they actually want to meet the fluortant and thus are sorry to have to wait.
:::success
Björn和其他$n-1$名孩子站成一排，準備見"fluortant"（給孩子口服氟化物治療的工作人員）。不同的孩子對"fluortant"有不同程度的害怕。這些孩子的編號從$1$到$n$，孩子$i$在隊列中的位置就是$i$。每個孩子都有相關的值$a_i$，表示他們對見"fluortant"的不情願程度。孩子$i$對他們在隊列中的位置感到幸福，幸福感的計算方式是$i⋅a_i$。一個孩子的$a_i$可以是負數，這意味著他們實際上希望見"fluortant"，因此為等待感到遺憾。
:::
Björn is the only child who is completely indifferent to meeting the fluortant, that is, he is the only child who has $a_i=0$. In addition, he is very kindhearted, so he decides to leave the queue and then enter the queue again somewhere so that the total happiness of everyone in the queue is as great as possible. Write a program that, given the values $a_i$ for all children, calculates the maximum sum of the happiness in the queue if Björn stands in an optimal place.
:::success
Björn是唯一一個對見"fluortant"完全不感興趣的孩子，也就是說，他是唯一一個$a_i=0$的孩子。此外，他非常善良，所以他決定離開隊伍，然後再重新進入隊伍的某個地方，以使隊伍中所有人的幸福總和最大化。請編寫一個程序，根據所有孩子的$a_i$值，計算Björn站在最佳位置時隊伍中的最大幸福總和。
:::

## Input

The first line contains an integer $n$, the number of children in the queue. On the next line are $n$ integers, where the $i$th number is $a_i$. $1≤n≤10^6$, $−1000≤a_i≤1000$.
:::success
第一行包含一個整數$n$，表示隊伍中的孩子數。接下來的一行包含$n$個整數，其中第$i$個數是$a_i$。$1≤n≤10^6$，$−1000≤a_i≤1000$。
:::

## Output

Print a line with one integer: the maximum total happiness in the queue.
:::success
輸出一行，包含一個整數：隊伍中的最大總幸福感。
:::

## Points

Your solution will be tested on several test case groups. To get points for a group your submission must pass all the test cases in the group.

| Group | Point value | Bounds | Other |
|-|-|-|-|
| $1$ | $32$ | $1≤n≤10^3$ | |
| $2$ | $12$ | $1≤n≤10^6$ | The sequence $a_1…a_n$ is non-decreasing. |
| $3$ | $11$ | $1≤n≤10^6$ | The sequence $a_1…a_n$ is non-increasing. |
| $4$ | $45$ | $1≤n≤10^6$ | |

:::success
你的解決方案將在多個測試案例組上進行測試。要獲得一個組的積分，你的提交必須通過該組中的所有測試案例。

| 組別 | 積分值 | 界限 | 其他 |
| ------ | ------- | ------ | ------ |
| 1 | 32 | $1≤n≤10^3$ | |
| 2 | 12 | $1≤n≤10^6$ | 數列$a_1…a_n$為非遞減的。 |
| 3 | 11 | $1≤n≤10^6$ | 數列$a_1…a_n$為非遞增的。 |
| 4 | 45 | $1≤n≤10^6$ | |
:::
## Explanation of example 1

Björn is last in the queue. The sum of the happiness is then $1⋅1+2⋅(−2)+3⋅0=−3$.

If Björn moves to the front of the queue, the sum of the happiness would be $1⋅0+2⋅1+3⋅(−2)=−4$, and in the middle it would be $1⋅1+2⋅0+3⋅(−2)=−5$. Both of these are worse alternatives.
:::success
Björn排在隊伍的最後。那麼幸福感的總和是$1⋅1+2⋅(−2)+3⋅0=−3$。

如果Björn移動到隊伍的最前面，幸福感的總和將是$1⋅0+2⋅1+3⋅(−2)=−4$，如果他站在隊伍中間，幸福感的總和將是$1⋅1+2⋅0+3⋅(−2)=−5$。這兩種情況都不如站在最後的選擇。
:::

### Sample Input 1

3
1 0 -2

### Sample Output 1

-3

### Sample Input 2

5
0 -8 1 1 5

### Sample Output 2

24

### Sample Input 3

7
2 -4 5 -3 0 -1 2

### Sample Output 3

7

{%hackmd @OJT/WAT %}