题目描述

幼儿园里有 $n$ 个小朋友排成了一排，每个小朋友都有一个欢乐值，其中，第 $i$ 个小朋友的欢乐值为 $a_i$。为了活跃气氛，现在对这 $n$ 个小朋友进行重新排列。

已知对于每个小朋友，如果其重新排列前为第 $i$ 位，重新排列后在第 $j$ 位，那么他的欢乐值就会增加为 $|i-j|\times a_i$。

请问，如何排列能够使得重新排列后，小朋友们的总欢乐值最大？输出重新排列后的最大的总的欢乐值之和。

输入格式

输入第一行一个整数 $n$，表示小朋友的人数。

接下来一行 $n$ 个整数 $a_i$，表示每个小朋友的欢乐值，用空格隔开。

输出格式

输出一个整数，表示答案。

样例

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

数据范围

• 对于 $100\%$ 的数据：$2≤n≤2000$，$1≤a_i≤10^9$。