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）。