Array Characteristic

Interview

Time limit2sMemory limit512 MB

Summary

Move one element to any position and maximize the weighted sum of A_i times its new index.

Level: Medium6 of 10
Topics: Array, Prefix sum
Solved: No attempts yet

Problem

You are given an integer array $A = A_1, A_2, \dots, A_N$ of length $N$ . The characteristic of the array is $C = \sum_{i=1}^{N} A_i \times i$ .

You can pick one element of the array and move it to any position. The destination can be the front of the array, the back of the array, or the position the element already occupies. Removing the element pulls every element behind it one step toward the front, and inserting it pushes every element from the destination onward one step toward the back. You make this move once.

Write a program that computes the maximum value of $C$ after one element is moved.

Input

The first line contains $N$ . ( $2 \le N \le 200{,}000$ )

The second line contains $A_1, A_2, \dots, A_N$ separated by spaces. ( $|A_i| \le 1{,}000{,}000$ )

Output

Print the maximum value of $C$ after one element is moved, on a single line.

Examples3

Example 1
Input
```
4
4 3 2 5
```
Expected output
```
39
```
Example 2
Input
```
5
1 1 2 7 1
```
Expected output
```
49
```
Example 3
Input
```
3
1 1 2
```
Expected output
```
9
```