CF631E.Product Sum

Blake is the boss of Kris, however, this doesn't spoil their friendship. They often gather at the bar to talk about intriguing problems about maximising some values. This time the problem is really special.

You are given an array a of length n. The characteristic of this array is the value — the sum of the products of the values a__i by i. One may perform the following operation exactly once: pick some element of the array and move to any position. In particular, it's allowed to move the element to the beginning or to the end of the array. Also, it's allowed to put it back to the initial position. The goal is to get the array with the maximum possible value of characteristic.

布莱克是克里斯的上司，但这并不影响他们的友谊。他们经常在酒吧聚会，讨论一些关于最大化某些值的有趣问题。这一次的问题尤为特别。

给你一个长度为 $ n $ 的数组 $ a $。该数组的特征值定义为：

即所有 $ a_i \times i $ 的和（下标从 1 开始）。
你恰好可以执行以下操作一次：任选数组中的一个元素，并将其移动到任意位置。特别地，允许将该元素移至数组开头或结尾；也允许将其放回原位。
目标是通过该操作，使数组的特征值尽可能大。

The first line of the input contains a single integer n (2 ≤ n ≤ 200 000) — the size of the array a.

The second line contains n integers a__i (1 ≤ i ≤ n, |a__i| ≤ 1 000 000) — the elements of the array a.

输入的第一行包含一个整数 $n$（$2 \leq n \leq 200\,000$）—— 数组 $a$ 的大小。

第二行包含 $n$ 个整数 $a_i$（$1 \leq i \leq n$，$|a_i| \leq 1\,000\,000$）—— 数组 $a$ 的元素。

Print a single integer — the maximum possible value of characteristic of a that can be obtained by performing no more than one move.

输出一个整数——在最多执行一次移动操作的前提下，数组 $a$ 的特征值所能达到的最大可能值。

In the first sample, one may pick the first element and place it before the third (before 5). Thus, the answer will be 3·1 + 2·2 + 4·3 + 5·4 = 39.

In the second sample, one may pick the fifth element of the array and place it before the third. The answer will be 1·1 + 1·2 + 1·3 + 2·4 + 7·5 = 49.

在第一个样例中，可以选取第一个元素并将其置于第三个元素（即 5）之前。因此，答案为 $3·1 + 2·2 + 4·3 + 5·4 = 39$。

在第二个样例中，可以选取数组的第五个元素并将其置于第三个元素之前。答案为 $1·1 + 1·2 + 1·3 + 2·4 + 7·5 = 49$。