Maximum Sum of Non-Adjacent Elements

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

In other words, let the input array be \(A = [a_0, a_1, \dots, a_{n-1}]\). You need to find a subset of indices \(S\) such that for every two consecutive indices \(i, j \in S\), \(|i - j| \geq 2\) and the sum \(\sum_{i \in S} a_i\) is maximized. If the maximum sum is negative, output 0.

inputFormat

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

outputFormat

Output a single integer which is the maximum sum of non-adjacent elements.

5
3 2 5 10 7

15