#描述#
给出长度为N的数列{A_i}，每次可以从最左边或者最右边取走一个数，第i次取数得到的价值是i * A_j。求价值之和最大的取数方案。

#格式#
##输入格式##
多组测试数据。每组的第一行，一个整数，表示数列长度N。
　　接下来N行，每行一个整数，表示数列A_i。

N &lt= 2000 , A_i &lt= 1000

##输出格式##
每组测试数据输出一个整数，表示最大的价值之和。

#样例1#
##样例输入1##

5
1
3
1
5
2

##样例输出1##

43

#限制#
1000ms
32768KB

#提示#

#来源#
daimin