题目描述

$FJ$ 有 $n$ ( $1 \le n \le 2000$ )个美味的食物，他想卖掉它们来赚钱给奶牛。这些食物放在一些箱子里，它们有些有趣的特性：

1. 这些食物被编号为 $1 \dots n$，每一天 $FJ$ 可以从这排箱子的头或者尾部取出食物去卖；

2. 跟美酒和奶酪一样，这些食物放得越久，年龄越大，价值越大，食物 $i$ 有一个初始的价值 $v(i)$；

3. 放了 $a$ 天后，年龄为 $a$ ，食物最终的价值为 $v(i)×a$；

给定每一个食物的初始价值 $v(i)$，请求出 $FJ$ 卖掉它们后可以获得的最大价值， 第一天出售的食物的年龄为 $1$ ，此后每增加一天食物的年龄就增加 $1$ 。

输入格式

第一行：一个整数 $n$；

第 $2n+1$ 行：每行为食物 $i$ 的初始价值 $v(i)$。

输出格式

一行：FJ 最终可以获得的最大价值。

样例

5
1
3
1
5
2

43

样例说明

$FJ$ 出售这些食物(初始价值 $1,3,1,5,2$)的顺序为：第一天卖掉第 $1$ 个，第二天卖掉第 $5$ 个，第三天卖掉第 $2$ 个，第四天卖掉第 $3$ 个，第五天卖掉第 $4$ 个，获得最大的价值 $1×1+2×2+3×3+4×1+5×5=43$。