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 \leq N \leq 10^6~

~1 \leq S_i \leq 10^9~

Subtask 1 [20%]

~1 \leq N, S_i \leq 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