Maximum Non-Adjacent Sum

You are given an array of integers. Your task is to find the maximum sum obtainable by summing a subset of these integers such that no two elements in the subset are adjacent in the original array.

Formally, if the array is given as \(A = [a_1, a_2, \ldots, a_n]\), you need to compute the maximum sum \(S\) defined by selecting indices \(i_1, i_2, \ldots, i_k\) where \(i_{j+1} - i_j \ge 2\) for all \(1 \leq j < k\). A common dynamic programming recurrence for this problem is:

\[ dp[i] = \max(dp[i-1], dp[i-2] + a_i)\quad \text{for } i \ge 2, \] with initial conditions \(dp[0] = a_1\) and \(dp[1] = \max(a_1, a_2)\) (assuming 1-indexing).

inputFormat

The first line contains a single integer \(n\) (\(0 \leq n \leq 10^5\)), which is the number of elements in the array. The second line contains \(n\) integers separated by spaces representing the elements of the array \(a_1, a_2, \ldots, a_n\).

outputFormat

Output a single integer: the maximum sum of a subset of non-adjacent elements.

## sample

5
3 2 5 10 7

15