活跃的幼儿 - 代码源竞赛平台

题目描述

有 $N$ 名幼儿从左到右站成一排，最初第 $i$ 名幼儿的活跃度为 $A_i$。

蜗蜗可以把他们重新排成任意一种顺序，但只能重新排列一次。若最初站在第 $i$ 个位置的幼儿最后站在第 $j$ 个位置，他会获得 $A_i\times |i-j|$ 点快乐值。

求所有幼儿的快乐值总和最大是多少。

输入格式

第一行包含一个整数 $N$，表示幼儿人数。

第二行包含 $N$ 个整数 $A_1,A_2,\ldots,A_N$，表示幼儿从左到右的活跃度。

输出格式

输出一行一个整数，表示最大的快乐值总和。

样例

3
1 2 3

9

2
5 5

10

样例解释

样例 1 中，最初的第 $1$、第 $2$、第 $3$ 名幼儿可以分别去第 $2$、第 $3$、第 $1$ 个位置，快乐值为 $1\times1+2\times1+3\times2=9$。

样例 2 中，交换两名幼儿的位置，两人各移动一步，快乐值为 $5+5=10$。

数据范围

对于 100% 的数据，保证 $2\le N\le 2000$，$1\le A_i\le 10^9$。