Maximum Nutrient Value

In this problem, you are given a list of integers representing nutrient values from different rows. Your task is to determine the maximum total nutrient value that can be collected under the constraint that you can't select nutrient values from two consecutive rows.

Formally, given an array (a[0 \ldots n-1]), you need to choose a subset of indices such that no two selected indices are consecutive, and the sum of the corresponding values is maximized. The recurrence relation for dynamic programming is given by:

(dp[i] = \max(a[i] + dp[i-2], dp[i-1])) with appropriate base cases.

If the array is empty, the answer is 0.

inputFormat

The first line of input contains an integer (n) ((0 \le n \le 10^5)) representing the number of nutrient rows. If (n > 0), the second line contains (n) space-separated integers, where each integer represents the nutrient value of the corresponding row.

outputFormat

Output a single integer which is the maximum total nutrient value that can be collected without selecting two consecutive rows.## sample

4
3 2 5 10

13