问题描述

具体描述见教材p260： FJ 有 n (1≤n≤2000)个美味的食物，他想卖掉它们来赚钱给奶牛。这些食物放在些箱子里，它们有些有趣的特性: (1) 这些食物被编号为 1~n ，每一天 F 可以从这排箱子的头部或者尾部取出食物去卖。 (2) 这些食物放得越久，年龄越大，价值越大，食物 i 有一个初始的价值 v(i) 。 (3) 放了a天后，年龄为 a，食物最终的价值为v(i)×a。 给定每一个食物的初始价值v(i)，请求出FJ卖掉它们后可以获得的最大价值， 第一天出售的食物的年龄为1，此后每增加一天食物的年龄就增加1。

格式

输入

第1行：一个整数 n； 第2n+1行：每行为食物i的初始价值 v(i)。

输出

1行：F最终可以获得的最大价值。

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

样例

5
1
3
1
5
2

43

限制

1s, 64MB.