活泼的幼童

题目描述

$N$ 名幼童排成一列,从左数第 $i$ 名幼童的活发度为 $A_i$。

你只能操作一次,可以将幼童按任意顺序重新排列。

当初从左数第 $x$ 名位置的幼童移动到从左数第 $y$ 名位置时,会产生 $A_x \times |x-y|$ 的快乐值。

求幼童快乐值总和的最大值。

输入格式

输入按以下格式从标准输入给出:

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

输出格式

输出幼童快乐值总和的最大值。

样例

4
1 3 4 2

20

如果把从左数第 $1$ 名幼童排到第 $3$ 位,第 $2$ 名排到第 $4$ 位,第 $3$ 名排到第 $1$ 位,第 $4$ 名排到第 $2$ 位,快乐值总和为 $1 \times |1-3|+3 \times |2-4|+4 \times |3-1|+2 \times |4-2|=20$。

6
5 5 6 1 1 1

58

6
8 6 9 1 2 1

85

数据范围

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