暂无测试数据。

题目描述

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

这些零食有以下这些有趣的特性：

• 零食按照 \(1 \ldots N\) 编号，它们被排成一列放在一个很长的盒子里。
  盒子的两端都有开口，FJ 每天可以从盒子的任一端取出最外面的一个。

• 与美酒和好吃的奶酪相似，这些零食储存得越久就越好吃。
  当然，这样 FJ 就可以把它们卖出更高的价钱。

• 每份零食的初始价值不一定相同。
  FJ进货时，第 \(i\) 份零食的初始价值为 \(v_i\)。

• 第 \(i\) 份零食如果在被买进后的第 \(a\) 天出售，则它的售价是 \(v_i*a\)。
  v_i 对应的是从盒子顶端往下的第 \(i\) 份零食的初始价值。

FJ告诉了你所有零食的初始价值，
并希望你能帮他计算一下，
在这些零食全被卖出后，
他最多能得到多少钱。
第一份零食在买进后的第 1 天售出，也就是说此时 \(a=1\)。
以后每过一天，\(a\) 的值就增加 1。

输入

第 1 行: 一个整数N，表示零食的总数
第 \(2 \ldots N+1\) 行: 第 \(i+1\) 行给出了从盒子顶端往下的第 \(i\) 份零食的初始价值 \(v_i\)

输出

一个整数，即FJ在卖完所有零食后的最大可能收益。

样例输入

5
1
3
1
5
2

样例输出

43

样例解释

FJ 一共进了5份零食。
第 1 天 FJ 可以选择出售第 1 份初始价值为 1 的零食，
或是第 5 份初始价值为 2 的零食。
FJ按照以下的顺序出售零食：1,5,2,3,4，
这样他的总收入就是 1*1+2*2+3*3+4*1+5*5=43。

数据范围限制

\(1 \leq N \leq 2000\);
\(1 \leq v_i \leq 1000\);

来源

基础篇补充7.11