FJ は大量の乳を出してお金を得る牛に $N$ 個 $(1 \le N \le 2000)$ のおいしいおやつを購入。一日一個売り、一定期間の収入を最大にします。

おやつの特徴：

• $1..N$ と番号を付け、両端が開く長箱に順に一列で保管。毎日どちらかの端から一個取り出せます。
• 良いワインやチーズのように熟成で質と価格が上がります。
• 一様でなく、質が良く本来の価値が高いものもあります。おやつ $i$ の価値は $v(i)$（$1 \le v(i) \le 1000$）。
• 牛は長く熟成したものに高く払い、熟成日数 $a$ なら $v(i)*a$ を払います。

箱の番号 $i$ 順の価値 $v(i)$ が与えられ、最適な販売順なら最大いくら得られますか？

初売りは第 1 日、熟成日数 $a=1$。以後毎日 1 増えます。

入力

• 1 行目：一整数 $N$。
• $2..N+1$ 行目：$i+1$ 行目は価値 $v(i)$。

出力

• 1 行目：販売の最大収入。

入出力例

入力 1

5
1
3
1
5
2

出力 1

43

注記

値 $1, 3, 1, 5, 2$ を番号 $1, 5, 2, 3, 4$ 順に売り、$1*1 + 2*2 + 3*3 + 4*1 + 5*5 = 43$ を得ます。

作者：Marco Gallotta（2005）。