Maximum Total Magic Value

You are given an integer n and an array of n integers representing the magic values of apples in consecutive segments. You cannot pick apples from two adjacent segments. Your task is to determine the maximum total magic value you can obtain by selecting segments under the constraint that no two chosen segments are adjacent.

The problem can be formulated using dynamic programming. Define a DP array where

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

with initial conditions

$$dp[0] = a_0, \quad dp[1] = \max(a_0, a_1).$$

The answer is the last element of the DP array, i.e., dp[n-1].

Example:

• Input: 5 and 3 2 7 10 12
• Output: 22

inputFormat

The first line contains a single integer n representing the number of segments. The second line contains n space-separated integers, where the i-th integer denotes the magic value of the i-th segment.

outputFormat

Output a single integer which is the maximum total magic value you can obtain by choosing non-adjacent segments.

## sample

5
3 2 7 10 12

22