Maximum Non-Adjacent Subsequence Sum

Given a sequence of integers, your task is to compute the maximum sum obtainable by selecting a subsequence in which no two elements are adjacent in the original list. Formally, if the input sequence is \(a_1, a_2, \dots, a_n\), you need to choose a non-empty subsequence \(a_{i_1}, a_{i_2}, \dots, a_{i_k}\) such that \(i_{j+1} - i_j \ge 2\) for all valid \(j\), and maximize the sum \(\sum_{j=1}^{k} a_{i_j}\). In the case when the input is empty, output 0.

Note: The subsequence must contain at least one element unless the list is empty. Even when all elements are negative, you should output the maximum (least negative) element.

inputFormat

The input is read from standard input (stdin). The first line contains a single integer \(n\) which represents the number of elements in the sequence. The second line contains \(n\) space-separated integers representing the elements of the list. If \(n = 0\), then there are no elements in the list.

outputFormat

Output a single integer on standard output (stdout) which is the maximum sum of a subsequence with no two adjacent elements.

4
3 2 5 10

13