Maximum Subset Sum (Non-Adjacent Elements)

You are given a list of n positive integers. Your task is to compute the maximum sum of a subsequence where no two elements are consecutive in the original list. In other words, if you choose an element, you cannot choose its immediate neighbors in the list.

Mathematically, if the list is represented as \(a_1, a_2, \dots, a_n\), you need to select a subset of indices \(I\) such that for any two indices \(i, j \in I\), \(|i - j| \ge 2\), and maximize \(\sum_{i \in I} a_i\).

Example 1: For the list [3, 2, 7, 10], one optimal subsequence is [3, 10] and the maximum sum is 13.

Example 2: For the list [3, 2, 5, 10, 7], one optimal subsequence is [3, 5, 7] and the maximum sum is 15.

Note: You must read the input from standard input (stdin) and write the output to standard output (stdout).

inputFormat

The first line of the input contains a single integer \(n\) (the number of elements). The second line contains \(n\) space-separated positive integers.

outputFormat

Print a single integer — the maximum possible sum of a subsequence with the given non-adjacency constraint.

4
3 2 7 10

13