Maximum Non-Adjacent Sum

You are given a list of non-negative integers. Your task is to compute the maximum sum of a subset of these numbers such that no two numbers in the subset are adjacent in the original list. Formally, if the array is represented as \(a_1, a_2, \ldots, a_n\), you want to find the maximum value of \(\sum_{i \in S} a_i\) where \(S\) is a subset of indices satisfying: for any two consecutive indices \(i\) and \(j\) in \(S\), \(|i-j| \ge 2\).

You can solve this problem using dynamic programming. One approach is to define a recurrence relation:

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

with initial conditions \(dp[0] = a_1\) (or 0 if the list is empty) and \(dp[-1] = 0\).

Read the input from stdin as described and output the result to stdout.

inputFormat

The first line contains an integer \(n\) denoting the number of elements in the array. The second line contains \(n\) space-separated integers representing the elements of the array.

Note: If \(n = 0\), the array is empty.

outputFormat

Output a single integer which is the maximum sum of non-adjacent elements in the array.

## sample

1
10

10

</p>