Maximum Non-Adjacent Sum

Given an array of integers, your task is to compute the maximum sum obtainable by selecting a subset of elements such that no two selected elements are adjacent in the array.

You can formulate the problem as follows: For each index \( i \), let \( dp[i] = \max(dp[i-1], dp[i-2] + a_i) \) for \( i \ge 2 \), where \( dp[i] \) represents the maximum sum achievable considering elements up to index \( i \). In other words, you decide for each element whether to include it (and then skip its immediate neighbor) or to exclude it.

For example, given the array [3, 2, 7, 10], selecting 3 and 10 yields a sum of 13, which is optimal.

inputFormat

The input is read from standard input (stdin) and consists of two lines:

1. The first line contains a single integer \( n \) (possibly 0) representing the number of elements.
2. The second line contains \( n \) space-separated integers representing the array.

If \( n = 0 \), the second line may be empty.

outputFormat

Output a single integer to standard output (stdout), which is the maximum sum of non-adjacent elements from the array.

4
3 2 7 10

13