N 个小朋友原来依次站在位置 1,2,\ldots,N，第 i 个位置上的小朋友的**活跃度**是 A_i。

老师要让他们重新站成一条直线（即给出 1..N 的一个**排列**作为新队伍）。原来站在位置 x 的小朋友被安排到新位置 y 时，他的**快乐值**是

A_i \times |x-y|

N 个小朋友的快乐值之和就是这次排队的**总分**。求总分最大能到多少。

注意：每个人的活跃度 A_i 跟着**人**走，跟他原来站的位置无关（新位置要自己安排）。

第一行一个整数 N。

第二行 N 个整数 A_i，其中 A_i 是原来站在位置 i 的那个小朋友的活跃度。

一行一个整数：能得到的最大总分。末尾换行。

**样例 #1 解释**

把新队伍安排成"原编号依次为 3,4,1,2"（即位置 1 站原来的第 3 个人、位置 2 站原来的第 4 个人、位置 3 站第 1 个人、位置 4 站第 2 个人）。四项快乐值分别是

4\times|3-1|=8,\quad 2\times|4-2|=4,\quad 1\times|1-3|=2,\quad 3\times|2-4|=6

合计 20，是所有排列里最大的。

| t1 | 20 | 20 | 2\le N\le6, A_i\le50 | 

| t2 | 20 | 40 | 7\le N\le8, A_i\le100 | 

| t3 | 20 | 60 | 10\le N\le11, A_i\le1000 | 

| t4 | 20 | 80 | 100\le N\le300, A_i\le10^9 |

| t5 | 20 | 100 | N=2000, A_i\le10^9 |