[ABC163E] 活跃的幼儿

题目描述

有N名幼儿排成一列，从左往右第i名幼儿的活跃度为Aᵢ。

你可以将幼儿们重新排列成任意顺序，仅一次。

当最初在左数第x位的幼儿移动到左数第y位时，会产生Aₓ×|x-y|的愉悦值。

求幼儿们的愉悦值总和的最大值。

输入格式

输入通过标准输入按以下形式给出：

N A₁ A₂ ... Aₙ

输出格式

输出幼儿愉悦值总和的最大值。

输入输出样例 #1

输入 #1

4
1 3 4 2

输出 #1

20

输入输出样例 #2

输入 #2

6
5 5 6 1 1 1

输出 #2

58

输入输出样例 #3

输入 #3

6
8 6 9 1 2 1

输出 #3

85

说明/提示

限制条件

• 2 ≤ N ≤ 2000
• 1 ≤ Aᵢ ≤ 10⁹
• 输入均为整数

样例解释 1

将左数第1名幼儿移到第3位，第2名幼儿移到第4位，第3名幼儿移到第1位，第4名幼儿移到第2位时，愉悦值总和为：1×|1-3| + 3×|2-4| + 4×|3-1| + 2×|4-2| = 20。