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

第一行，一个整数，表示数列长度N。 接下来N行，每行一个整数，表示数列。

一个整数，表示最大的价值之和。

5
1
3
1
5
2

43

样例说明：