Maximum Sum of Two Non-overlapping Subarrays in a Circular Sequence

You are given a circular sequence of integers \(a\) of length \(n\). In the circular structure, \(a_1\) and \(a_n\) are considered adjacent. Your task is to select two non-overlapping, non-empty contiguous segments (subarrays) from the circular sequence such that the sum of their elements is maximized.

Note: A contiguous segment in the circular sequence may wrap around from the end to the beginning. However, the two chosen segments must not share any common element.

For example, if the entire array is taken by one segment then the other segment would be empty, which is not allowed.

Input format: The first line contains an integer \(n\) representing the number of elements in the sequence. The second line contains \(n\) space-separated integers \(a_1, a_2, \ldots, a_n\).

Output format: Output a single integer representing the maximum possible sum of the elements in the two selected segments.

It is guaranteed that there exists at least one valid way to choose two segments.

inputFormat

The input begins with an integer \(n\) on the first line. The second line contains \(n\) space-separated integers, representing the elements of the circular sequence.

Example:

5
1 2 3 4 5

outputFormat

Output a single integer which is the maximum sum that can be achieved by selecting two non-overlapping contiguous segments from the circular sequence.

Example:

15

sample

5
1 2 3 4 5

15