Maximum Possible Card Sum

Given a list of integer card values, determine the maximum sum you can obtain by selecting non-adjacent cards. In other words, no two chosen cards should be consecutive in the list. This is a classic dynamic programming problem similar to the "House Robber" problem, with the twist that the list may contain negative numbers. If all cards are negative, then the answer is the maximum (i.e., the least negative) value.

Formally, if you are given a sequence \(a_1, a_2, \ldots, a_n\), you need to choose a subset of these numbers such that for any two chosen indices \(i\) and \(j\) (with \(i \neq j\)), \(|i - j| > 1\), and so that the sum of the chosen numbers is maximized. The recurrence relation used in dynamic programming is:

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

For example, if the input is [3, 2, 5, 10, 7], one way to obtain the maximum sum is to select cards with values 3, 5, and 7, giving a sum of 15.

inputFormat

The first line of input contains an integer \(n\) representing the number of cards. The second line contains \(n\) space-separated integers representing the values of the cards.

outputFormat

Output a single integer which is the maximum sum obtainable by selecting non-adjacent cards.

## sample

5
3 2 5 10 7

15

</p>