Max Non-Adjacent Subsequence Sum

You are given an array of n integers. Your task is to compute the maximum sum obtained by selecting a subsequence such that no two selected elements are adjacent in the original array.

Note that if the array contains all negative numbers, the answer should be 0 (i.e. it is better to choose no element). Otherwise, you should choose the optimal elements to maximize the sum.

Example 1:

Input: [3, 2, 7, 10]
Output: 13

Example 2:

Input: [5, -10, 20, -15, 25]
Output: 50

Hint: Use dynamic programming to keep track of the maximum sum including or excluding the current element.

inputFormat

The input is read from standard input and has the following format:

• The first line contains an integer n — the number of elements in the array.
• The second line contains n space-separated integers representing the array elements.

outputFormat

Output a single integer — the maximum sum of non-adjacent elements. The output should be written to standard output.

## sample

4
3 2 7 10

13