题目描述：

$FJ$ 为那些产奶量高的奶牛购买了 $N（1 ≤ N ≤ 2000）$份美味的零食，这些奶牛会为产奶获得报酬，而 $FJ$ 想通过售卖零食在一段时间内最大化自己的收益。每天 $FJ$ 会卖出一份零食，他希望最大化这段时间内获得的总金钱。

这些零食之所以有趣，有以下几个原因：

$1$.这些零食编号为 $1$ 到 $N$，并按顺序存放在一个两端开口的长盒子里（即排成一列）。每天，$FJ$ 可以从当前剩余零食的左端或右端取出一份零食。

$2$.就像美酒和美味的奶酪一样，这些零食随着 “年龄” 的增长而增值，能卖出更高的价格。

$3$.零食的品质参差不齐：有些零食品质更好，具有更高的内在价值。第 $i$ 个零食的价值为 $v (i)（1 ≤ v (i) ≤ 1000）$。

$4$.奶牛会为存放时间更长的零食支付更高的价格：一份 “年龄” 为 $a$ 的零食，奶牛会支付 $v (i)×a$ 的价格。

给定盒子中按索引 $i$ 顺序排列的每个零食的价值 $v (i)$，如果 $FJ$ 以最优顺序出售这些零食，他能获得的最大价值是多少？

第一份零食在第 $1$ 天出售，年龄 $a=1$。之后的每一天，零食的年龄都会增加 $1$。

输入：

第一行：一个整数 $N$

第二行到第 $N+1$ 行：第 $i+1$ 行包含第 $i$ 个零食的价值 $v (i)$

输出：

第一行：$FJ$ 通过出售零食能获得的最大收益

输入数据1

5
1
3
1
5
2

输出数据1

43

提示：

样例解释： $共有 5 份零食。第一天，FJ 可以选择出售第 1 份零食（价值 1）或第 5 份零食（价值 2）。 FJ 按以下索引顺序出售零食（价值分别为 1, 3, 1, 5, 2）：1, 5, 2, 3, 4，计算收益为：1×1 + 2×2 + 3×3 + 4×1 + 5×5 = 43$。

来源：

美国计算机科学奥林匹克竞赛（USACO）2006 年 2 月 黄金级与白银级