Maximum Non-Adjacent Sum

You are given a list of integers representing happiness values. Your task is to compute the maximum sum obtainable by selecting a subset of these values such that no two selected values are adjacent in the original list.

In other words, if the list is denoted by \(a_1, a_2, \dots, a_n\), you need to choose some indices \(i_1, i_2, \dots, i_k\) with the condition that \(|i_j - i_{j-1}| > 1\) for all \(j\), and maximize the sum \(a_{i_1} + a_{i_2} + \cdots + a_{i_k}\).

The typical dynamic programming recurrence for this problem is:

$$dp[i] = \max(dp[i-1], dp[i-2] + a_i)$$

where \(dp[i]\) represents the maximum sum considering elements up to index \(i\).

inputFormat

The input consists of two lines:

• The first line contains a single integer \(n\) indicating the number of elements in the list.
• The second line contains \(n\) space-separated integers representing the happiness values.

outputFormat

Output a single integer, the maximum sum of non-adjacent values that can be obtained.

## sample

1
5

5

</p>