小x和室友总共 $n$ 人，组团去打一款游戏，总共有 $n$ 台电脑供他们使用，一人一台，最开始，第 $i$ 个人使用第 $i$ 台电脑。

小x评估了每个人的能力值和临场发挥值。

第 $i$ 个人的能力值为 $a_i$。

而他们的临场发挥值由能力值和他们所使用的电脑决定。

小x和他的室友喜欢换来换去。

他们惊奇的发现：如果第 $i$ 个人从第 $x$ 台电脑换到了第 $y$ 台电脑，那么第 $i$ 个人的临场发挥值会增加 $|x-y|*a_i$。

现在他们可以重新任意分配一次电脑。

小x想知道他们的临场发挥值最多会增加多少？

第一行一个整数 $n$ $(2 \leq n \leq 2000)$。

第二行 $n$ 个整数 $a_1,a_2,……,a_n$ $(1 \leq a_i \leq 10^9)$。

一个整数，表示临场发挥值最大增加的数量。

对于样例1，假设第 $i$ 个人的位置为 $c_i$，从 $[1,2,3,4]$ 更换为 $[3,4,1,2]$，临场发挥值增加： $1 \times |1-3|+3 \times |2-4|+4 \times |3-1|+2 \times |4-2|=20$