题目描述

小美最近开了一家薯片店，她进了一批特别的薯片。这些薯片按编号 1 到 N 排成了一列，放在一个特别的展示柜里。展示柜的两端都有开口，小美每天只能从展示柜的任意一端取出最外面的薯片来卖。

薯片的出售日期越久，味道越好，所以卖出的价钱也会更高。每袋薯片的初始价值不同，第 i 袋薯片的初始价值为 Vi。薯片被售出的那天，它的售价为 Vi×a，其中 a 表示卖出的天数。

小美希望你能帮她设计一个策略，在薯片全部售出后，赚到最多的钱。

输入 第 1 行包含一个整数 N（表示薯片的数量）。

第 2 行到第 N+1行，第 i+1 行包含一个整数 Vi（表示第 i 袋薯片的初始价值）。

1≤N≤2000，1≤Vi≤1000

输出

输出一个整数，表示通过销售这些薯片可以获得的最大收益。

样例输入

4 4 7 2 6

样例输出

50

提示

小美按以下顺序售出薯片：第 1 天卖 1 号，第 2 天卖 4 号，第 3 天卖 3 号，第 4 天卖 2 号。计算方式为：14 + 26 + 32 + 47 = 50。