Fiona is making a decorative wreath to hang outside of the math club room. She is almost done making the wreath and realized that she has forgotten to put a bow on the wreath! All good wreaths must have a bow. However, where should she place the bow?

Fiona took the wreath and identified $N$ partitions in the wreath. She then assigned the $i^{\text{th}}$ partition a festive score of $S_i$. Since the wreath is circular, the index of the next clockwise partition of $N$ will be $1$. She will then choose a spot to place a bow. When a bow is placed at partition $i$, the left score $L$ is defined as the sum of $S_i$ festive scores counter-clockwise from the $i^{\text{th}}$ partition, while the right score $R$ is defined as the sum of $S_i$ festive scores clockwise from the $i^{\text{th}}$ partition. The total score is equal to $|L-R|+S_i$.

Note: $L$ and $R$ can include a partition multiple times.

What is the maximum possible total score that can be achieved?

Constraints

$1\le N\le {10}^6$

$1\le S_i\le {10}^9$

Subtask 1 [20%]

$1\le N,S_i\le {10}^3$

Subtask 2 [80%]

No additional constraints.

Input Specification

The first line contains the integer $N$.

The second line contains $N$ space separated integers, where the $i^{\text{th}}$ integer represents the festive score of the $i^{\text{th}}$ partition.

Output Specification

Output a single integer, the maximum total score possible.

Sample Input 1

5
1 3 5 3 1

Sample Output 1

7

Explanation for Sample 1

An optimal solution is to choose the $2^{\text{nd}}$ partition.

$3+|(1+1+3)-(5+3+1)|=7$

Sample Input 2

4
1 2 2 4

Sample Output 2

4