布莱克是克里斯的老板,但这并不会破坏他们的友谊。他们经常聚集在酒吧讨论有关最大化某些价值的有趣问题。这次的问题确实很特别。
给定一个长度为 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。