Non-Adjacent Maximum Sum

You are given a list of integers. Your task is to find the maximum possible sum of a subsequence such that no two selected integers are adjacent in the original list.

Formally, let the input list be \(a_1, a_2, \dots, a_n\). You need to select a subset of indices \(I\) such that for every \(i, j \in I\) with \(|i - j| = 1\), the two indices are not both selected, and maximize the total sum \(\sum_{i \in I} a_i\). If all possible selections yield a negative sum, output 0.

This can be formulated in dynamic programming using the recurrence:

[ dp[i] = \max(dp[i-1], dp[i-2] + a_i) \quad \text{for } i \ge 2, ]

with appropriate base conditions. Use this formula to solve the problem.

inputFormat

The input is given via standard input (stdin) and consists of two lines:

• The first line contains a single integer \(n\) — the number of elements in the array. \(n\) can be zero.
• If \(n > 0\), the second line contains \(n\) space-separated integers representing the elements of the array.

outputFormat

Output a single integer (on stdout) which represents the maximum sum of a subsequence with the constraint that no two chosen numbers are adjacent in the original list.

## sample

5
3 2 5 10 7

15

</p>