Maximum Circular Subarray Sum

You are given a circular array of n integers. In a circular array, the end of the array wraps around to the beginning. Your task is to find the maximum possible sum of a contiguous subarray, where the subarray may be formed by wrapping around from the end to the beginning.

Formally, let the array be \(a_1, a_2, \ldots, a_n\). A subarray may consist of elements \(a_i, a_{i+1}, \ldots, a_n, a_1, \ldots, a_j\) (with \(1 \le j < i \le n\) allowed), and its sum is defined as \(\sum_{k=i}^{n}a_k+\sum_{k=1}^{j}a_k\). Alternatively, if the subarray does not wrap around, then the sum is just \(\sum_{k=i}^{j}a_k\). You need to compute the maximum such sum.

Note: If all numbers are negative, the answer is the maximum element.

inputFormat

The first line contains a single integer n indicating the number of elements in the array.

The second line contains n space-separated integers representing the elements of the array.

You should read the input from stdin.

outputFormat

Output a single integer, which is the maximum possible sum of any contiguous subarray in the circular array. Write your answer to stdout.

5
1 -2 3 4 -1

7