题目描述

$n$ 位同学站成一排，左起第 $i$ 个位置同学的活跃指数是 $a_i$.

现在重新要对 $n$ 位同学进行排队，当原来从左起第 $x$ 个位置的同学移动到从左起第 $y$ 个位置时，该同学将给团队带来 $A_x \times|x−y|$ 的活跃度。

如何排队，使得团队总活跃度最大，求最大活跃度。

输入格式

第一行，一个整数 $n$

接下来一行 $n$ 个整数，表示活跃指数 $a_i$.

输出格式

一个整数，表示最大总活跃度。

4
1 3 4 2

20

6
1 3 5 7 10 12

124

10
10 9 8 7 6 5 4 3 2 1

298

数据规模与约定

所有数据满足：$2 \le n \le 2000$, $1 \le a_i \le 10^9$.

$Subtask1:$ $2 \le n \le 10 ,1 \le a_i \le 10^3$ , $20$ 分

$Subtask2:$ $2 \le n \le 2000$ , 满足性质对于 $i \in [2,n]$ , 满足 $a_{i-1}\le a_i$ 或 $a_{i} \le a_{i-1}$ , $20$ 分

$Subtask3:$ $2 \le n \le 2000$, $1 \le a_i \le 10^9$, $60$ 分