Problem H
フルオルタント

ビョルンと $n-1$ 人の他の子供たちは、「フルオルタント」（フッ化物の管理者、子供たちにフッ化物の治療をするために学校に来る）に会うために並んでいます。 子どもたちは、多かれ少なかれフルオルタントを怖がっています。 子供たちには$1$から$n$までの番号が振られており、子供$i$は列の中の位置$i$にいます。 子供 $i$ は、関連する値 $a_ i$ も持っており、子供がフルオルタントに会うことにどれだけ消極的かを示しています。 子供 $i$ が、列に並んでいることで感じる幸せは、 $i \cdot a_ i$ です。 $a_ i$ は、負の値になることもあります。これは、フルオルタントに会いたくて待たされるのが残念だということを意味します。

ビョルンだけが、フルオータントに会うことに全く無関心、つまり、$a_ i = 0$です。 さらに、彼は非常に優しいので、一旦列を抜けて、列の中のみんなの幸せの合計ができるだけ大きくなるように、どこかで再び列に入ることにします。 子供たちに対する値 $a_ i$ が与えられたときに、ビョルンが最適な場所に入った場合の幸せの合計の最大値を計算するプログラムを書いてください。

入力

最初の行には整数$n$が含まれます。これは、並んでいる子供の人数を表します。 次の行には、$n$個の整数が含まれます。$i$番目の数が$a_ i$です。$1 \leq n \leq 10^6 $, $-1\, 000 \leq a_ i \leq 1\, 000$です。

出力

列の幸せの合計の最大値を出力してください。

得点

あなたのソリューションは、いくつかのテストケースグループでテストされます。 グループのポイントを得るためには、グループ内のすべてのテストケースに成功しなければなりません。

サンプル1の説明

ビョルンは列の最後尾にいます。幸せの合計値は $1 \cdot 1 + 2\cdot (-2) + 3 \cdot 0 = -3$ です。

ビョルンが列の先頭に移動すると、幸せの合計値は $1 \cdot 0 + 2 \cdot 1 + 3 \cdot (-2) = -4$ となり、中央に移動すると $1 \cdot 1 + 2 \cdot 0 + 3 \cdot (-2) = -5$ となります。 どちらもより悪い結果となります。

3
1 0 -2

-3

5
0 -8 1 1 5

24

7
2 -4 5 -3 0 -1 2

7