No submission language available for this problem.

Background

Special for beginners, ^_^

Description

约翰经常给产奶量高的奶牛发特殊津贴，于是很快奶牛们拥有了大笔不知该怎么花的钱。为此，约翰购置了 $N$（$1 \leq N \leq 2000$） 份美味的零食来卖给奶牛们。每天约翰售出一份零食。当然约翰希望这些零食全部售出后能得到最大的收益，这些零食有以下这些有趣的特性：

• 零食按照 $1, \ldots, N$ 编号，它们被排成一列放在一个很长的盒子里。盒子的两端都有开口，约翰每天可以从盒子的任一端取出最外面的一个。
• 与美酒与好吃的奶酪相似，这些零食储存得越久就越好吃。当然，这样约翰就可以把它们卖出更高的价钱。
• 每份零食的初始价值不一定相同。约翰进货时，第i份零食的初始价值为 $V_i$（$1 \leq V \leq 1000$）。
• 第i份零食如果在被买进后的第 $a$ 天出售，则它的售价是 $V_i \times a$。

$V_i$ 的是从盒子顶端往下的第i份零食的初始价值。约翰告诉了你所有零食的初始价值，并希望你能帮他计算一下，在这些零食全被卖出后，他最多能得到多少钱。

Format

Input

第 $1$ 行：一个整数 $N$。

第 $2$ 至 $N+1$ 行：第 $i+1$ 行包含 $v(i)$ 的值。

Output

通过销售这些零食能够实现的最大收入

Samples

5
1
3
1
5
2

43

Limitation

样例一解释：

总共有五个零食。在第一天，可以选择出售零食 $1$（价值为 $1$）或者零食 $5$（价值为 $2$）。

按照以下顺序出售了这些零食（它们的价值分别为 $1、3、1、5、2$）：$1$ 号、$5$ 号、$2$ 号、$3$ 号、$4$ 号，使得 $1 \times 1 + 2 \times 2 + 3 \times 3 + 4 \times 1 + 5 \times 5 = 43$，这是最大的收入。

1s, 1024KiB for each test case.