ABC163——Task E：Active Infants - Problem - MYOJ

Problem5323--ABC163——Task E：Active Infants

5323: ABC163——Task E：Active Infants

_{[Creator : ]}

Time Limit : 1.000 sec Memory Limit : 256 MiB

Submit Solved: 1 Submit Num: 1 Statistics ShowOff!

Description

There are $N$ children standing in a line from left to right. The activeness of the $i$ -th child from the left is $_{i}$ .

You can rearrange these children just one time in any order you like.

When a child who originally occupies the $x$ -th position from the left in the line moves to the $y$ -th position from the left, that child earns $_{x} \times | x - y |$ happiness points.

Find the maximum total happiness points the children can earn.

Input

Input is given from Standard Input in the following format:

N
A₁ A₂ ... A_N

Output

Print the maximum total happiness points the children can earn.

Sample 1 Input

4
1 3 4 2

Sample 1 Output

HINT

【样例数据 1 说明】
If we move the

1

1-st child from the left to the

3

3-rd position from the left, the

2

2-nd child to the

4

4-th position, the

3

3-rd child to the

1

1-st position, and the

4

4-th child to the

2

2-nd position, the children earns

1 \times | 1 - 3 | + 3 \times | 2 - 4 | + 4 \times | 3 - 1 | + 2 \times | 4 - 2 | = 20

1×|1−3|+3×|2−4|+4×|3−1|+2×|4−2|=20 happiness points in total.
【样例数据 2 输入】

6
5 5 6 1 1 1

【样例输出 2 输出】

【样例数据 2 输入】

6
8 6 9 1 2 1

【样例输出 2 输出】

【数据范围】

$2 \leq N \leq 2000$
$1 \leq_{i} \leq^{9}$
All values in input are integers.

【题目出处】
AtCoder Beginner Contest 163，Task E。https://atcoder.jp/contests/abc163/tasks/abc163_e

Source/Category

AtCoder_ABC 100.163.ABC163

Submit