Maximum Circular Subarray Sum

Given a circular array of integers, your task is to compute the maximum sum of any contiguous subarray. Note that the array is circular, meaning that after the last element, it wraps back to the first element.

Formally, given a circular array \(A = [a_0, a_1, \dots, a_{n-1}]\), you need to find the maximum possible sum of a subarray. This can be expressed as:

\( \text{result} = \max( \text{max\_subarray\_sum},\; \text{total\_sum} - \text{min\_subarray\_sum} ) \)

where:

• \( \text{max\_subarray\_sum} \) is the maximum subarray sum computed using Kadane's algorithm, and
• \( \text{min\_subarray\_sum} \) is the minimum subarray sum (which can be computed by modifying Kadane's algorithm on the inverted array).

Be careful to handle edge cases, such as when all numbers are negative.

inputFormat

The input is read from standard input (stdin) and has the following format:

1. The first line contains an integer \(n\) representing the number of elements in the array.
2. The second line contains \(n\) space-separated integers representing the elements of the array.

outputFormat

Print a single integer — the maximum sum of any contiguous subarray in the circular array to standard output (stdout).

## sample

4
8 -1 3 4

15