← 返回题目列表

Codeforces · 631/E

E. 产品总和

中文机器翻译题面 查看原题

布莱克是克里斯的老板,但这并不会破坏他们的友谊。他们经常聚集在酒吧讨论有关最大化某些价值的有趣问题。这次的问题确实很特别。

给定一个长度为 n 的数组 a。该数组的特征是值 $$c = \sum_{i=1}^{n} a_i \cdot i$$ — 值 ai 与 i 的乘积之和。人们可以执行一次以下操作:选取数组中的某个元素并移动到任意位置。特别是,允许​​将元素移动到数组的开头或结尾。另外,还可以将其放回初始位置。目标是获得具有最大可能特征值的数组。

输入

输入的第一行包含一个整数 n (2 ≤ n ≤ 200 000) — 数组 a 的大小。

第二行包含 n 个整数 ai (1 ≤ i ≤ n, |ai| ≤ 1 000 000) — 数组 a 的元素。

输出

打印一个整数 — 通过执行不超过一次的移动可以获得的 a 特征的最大可能值。

示例

输入 #1

4
4 3 2 5

输出 #1

39

输入 #2

5
1 1 2 7 1

输出 #2

49

输入 #3

3
1 1 2

输出 #3

9

注意

在第一个示例中,可以选择第一个元素并将其放置在第三个元素之前(5 之前)。因此,答案为 3·1 + 2·2 + 4·3 + 5·4 = 39。

在第二个示例中,可以选择数组的第五个元素并将其放置在第三个元素之前。答案是 1·1 + 1·2 + 1·3 + 2·4 + 7·5 = 49。