古董

拍卖师准备了 N 件古董进行拍卖。这些古董有以下重要特性：

陈列规则：所有古董按 1、……、N 编号陈列在一条长廊中，每天拍卖师只能从长廊任一端取出一件古董拍卖。

升值效应：古董拍卖顺序直接影响成交价。若第 i 件古董在第 a天拍卖，成交价为 Vi×a（Vi 为初始估价）。

价值分布：第 i 件古董的初始估价 Vi 取决于其陈列位置——从入口端开始，第 i 个展柜内的古董估价为Vi。

拍卖师需要制定最优拍卖顺序，最大化总成交额。请帮助他计算出古董全部售出后的最大收益。

时间限制：1000ms内存限制：256MB

输入格式

第一行：古董数量 N；

接下来 n 行：古董初始估价序列 V1～VN；

输出格式

一行整数，表示最大总收益。

输入样例

5
1
3
1
5
2

输出样例

43

数据范围：

1≤N≤2000，1≤Vi≤1000。