题目描述

There are $N$ children standing in a line from left to right. The activeness of the $i$-th child from the left is $A_i$.

You can rearrange these children just one time in any order you like.

When a child who originally occupies the $x$-th position from the left in the line moves to the $y$-th position from the left, that child earns $A_x \times |x-y|$ happiness points.

Find the maximum total happiness points the children can earn.

从左到右有 $N$ 个孩子站成一排。左边第 $i$ 个孩子的活跃度是 $A_i$ 。

你可以把这些孩子按照任意顺序重新排列一次。

当原本排在左起第 $x$ 个位置的孩子移动到左起第 $y$ 个位置时，这个孩子就会获得 $A_x \times |x-y|$ 个快乐点数。

求孩子们能获得的最大幸福点数。

输入格式

输入内容按以下格式标准输入：

$N$
$A_1$ $A_2$ $...$ $A_N$

输出格式

打印孩子们能获得的最高幸福总分。

样例 #1

样例输入 #1

4
1 3 4 2

样例输出 #1

20

样例 #2

样例输入 #2

6
5 5 6 1 1 1

样例输出 #2

58

样例 #3

样例输入 #3

6
8 6 9 1 2 1

样例输出 #3

85

说明

数据规模与约定

• $2 \leq N \leq 2000$
• $1 \leq A_i \leq 10^9$
• 所有输入值均为整数。

样例 $1$ 解释

如果我们把左边的 $1$ （st）个孩子移动到左边的 $3$ （rd）个位置，把 $2$ （nd）个孩子移动到 $4$ （th）个位置，把 $3$ （rd）个孩子移动到 $1$ （st）个位置，把 $4$ （th）个孩子移动到 $2$ （nd）个位置，那么孩子们一共获得了 $1 \times |1-3|+3 \times |2-4|+4 \times |3-1|+2 \times |4-2|=20$ 个幸福点数。