Maximum Non-Adjacent Sum

You are given a list of integers. Your task is to compute the maximum possible sum of a subsequence of the list such that no two elements in the subsequence are adjacent in the original list.

In mathematical terms, given an array \(A = [a_1, a_2, \dots, a_n]\), find the maximum sum \(S\) such that if \(a_i\) is included in \(S\), then \(a_{i-1}\) and \(a_{i+1}\) are not included. Formally, you want to maximize

[ S = \sum_{i \in I} a_i ]

subject to the constraint

[ \forall i, j \in I: |i-j| \ge 2. ]

Note that if all numbers are negative, the answer is defined to be 0.

Example:

Input: 5
       3 2 5 10 7
Output: 15

inputFormat

The first line contains a single integer \(n\), the number of elements in the list. The next line contains \(n\) space-separated integers denoting the elements of the list. If \(n = 0\), the list is empty.

outputFormat

Output a single integer representing the maximum sum of non-adjacent elements from the list.

## sample

0

0

</p>