FJ 買了 $N$ 份 $(1 \le N \le 2000)$ 美味零食，給因產大量奶而獲得錢的牛。每天賣一份，希望在一段時間內收入最大。

零食有趣之處很多：

• 編號 $1..N$ 的零食按順序排成單列，放在兩端開口的長盒中。每天 FJ 可從任一端取一份。
• 像好酒、美味乳酪，零食越陳越好、價格越高。
• 品質不同，有些更好、內在價值更高。零食 $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

說明

FJ 按編號 $1, 5, 2, 3, 4$ 出售價值 $1, 3, 1, 5, 2$ 的零食，收入 $1*1 + 2*2 + 3*3 + 4*1 + 5*5 = 43$。

出題：Marco Gallotta（2005）。