【问题描述】

有n个石子围成一圈，每个石子都有一个权值a[i]，你需要取一些石子，每取个石子的得分是a[i]*d，其中：d表示被取石子到它两边被取了的石子位置，所经过未取的石子的个数和。

现在你可以取若干石子，使得分最大。

题目说明见下图：

注意若取：2，7，34后，你的得分为2*(2+1)+34*(2+2)+7*(1+2)=163（不是最大得分）；

【输入格式】

第1行一个整数n。

接下来n行，每行一个整数a[i]。

【输出格式】

仅一个整数，表示最大得分。

【输入样例】

5 1 2 3 4 20

【输出样例】

80

【样例说明】

选择1个权值为20的石子，d=4,20*4=80是最大得分

【数据规模】

对于30%的数据，n≤60；

对于40%的数据，n≤300；

对于100%的数据，n≤100000，1≤a[i]≤100000。