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

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

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

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

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

输入格式

第一行：古董数量 N

接下来 n 行：古董初始估价序列 V_1 ∼ V_N

输出格式

一行整数表示最大总收益

输入样例

5
1
3
1
5
2

输出样例

43

说明提示

【数据范围】

1 ≤ N ≤ 2000

1 ≤ V_i ≤ 1000

限制

时间限制：1000ms，内存限制：256MiB