Description

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

Input

多组测试数据。每组的第一行，一个整数，表示数列长度N。 　　接下来N行，每行一个整数，表示数列A_i。
N <= 2000 , A_i <= 1000

Output

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

Sample

Input

5
1
3
1
5
2

Output

43

Source: daimin