Maximum Non-Adjacent Sum in a Circular Array

You are given a circular array of integers \(a_0, a_1, \ldots, a_{n-1}\). In a circular array, the first and last elements are considered adjacent. Your task is to compute the maximum sum you can obtain by selecting a subset of non-adjacent elements. Remember that if you pick an element, you cannot pick its adjacent elements, and due to the circular nature, \(a_0\) and \(a_{n-1}\) are also adjacent.

Mathematically:

Find the maximum value of \(\sum_{i \in S} a_i\) subject to the condition that for any two selected indices \(i\) and \(j\) (with \(i \neq j\)), they are not adjacent in the circular sense. That is, if \(i \in S\), then \((i-1) \mod n \notin S\) and \((i+1) \mod n \notin S\).

Input/Output: The input will be provided via standard input and the output via standard output.

inputFormat

The input consists of two lines:

• The first line contains a single integer \(n\) (\(1 \leq n \leq 10^5\)), representing the number of elements in the array.
• The second line contains \(n\) space-separated integers \(a_0, a_1, \ldots, a_{n-1}\), where each \(a_i\) is the value of the \(i\)-th element.

outputFormat

Output a single integer -- the maximum sum of non-adjacent elements in the circular array.

1
10

10