Question
Circular Energy Harvest
In the city of Loopville, there is a circular road with KaTeX can only parse string typed expression checkpoints placed along it, forming a circular array. Each checkpoint has an energy value, which can be positive, negative, or zero.
A traveler wants to collect energy by choosing a contiguous sequence of checkpoints.
Because the road is circular, the sequence may wrap around from the end of the array back to the beginning.
However, each checkpoint can be visited at most once, meaning the chosen segment cannot include any element more than one time.
Your task is to determine the maximum possible sum of energy that the traveler can collect by selecting such a contiguous segment.
Input
The first line contains a single integer KaTeX can only parse string typed expression — the number of checkpoints.
The second line contains KaTeX can only parse string typed expression integers representing the energy values at the checkpoints — KaTeX can only parse string typed expression.
The second line contains KaTeX can only parse string typed expression integers representing the energy values at the checkpoints — KaTeX can only parse string typed expression.
Output
Print a single integer — the maximum subarray sum, considering the array to be circular and each element usable only once.
Example
Input
5
8 -1 3 4
Output
15
Explanation
The traveler selects the contiguous segment KaTeX can only parse string typed expression, which wraps around the circular array. The sum is KaTeX can only parse string typed expression, and no checkpoint is counted more than once.
5
8 -1 3 4
Output
15
Explanation
The traveler selects the contiguous segment KaTeX can only parse string typed expression, which wraps around the circular array. The sum is KaTeX can only parse string typed expression, and no checkpoint is counted more than once.