临场发挥
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

小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

输入

复制 
4
1 3 4 2

输出

复制 
20

说明

假设第 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
示例2

输入

复制 
6
8 6 9 1 2 1

输出

复制 
85