题目描述

农夫约翰买下了 $n$ 份零食，并将它们排成一排。第 $i$ 份零食的初始售价为 $v_i$。

他计划每天卖出一份零食。每天只能从当前队列的最左端或最右端取出一份出售。由于零食存放时间越久越珍贵，第 $i$ 天卖出的零食售价为它的初始售价乘以当天的天数 $i$。

请你帮助农夫约翰安排出售顺序，使卖出所有零食获得的总收入最大，并输出这个最大收入。

输入格式

第一行输入一个整数 $n$，表示零食的数量。

接下来 $n$ 行，每行输入一个整数 $v_i$，表示第 $i$ 份零食的初始售价。

输出格式

输出一个整数，表示能够获得的最大总收入。

样例

5
1
3
1
5
2

43

数据范围

对于所有测试数据：

• $1\le n\le2000$；
• $1\le v_i\le1000$。

注意，答案可能超过 32 位有符号整数的范围。