Maximum Non-Adjacent Sum

You are given an array of positive integers. Your task is to compute the maximum sum which can be obtained by summing a subset of the array's elements, under the constraint that no two elements chosen are adjacent in the original array.

Formally, given an array \(A = [a_1, a_2, \dots, a_n]\), select a set of indices \(\{i_1, i_2, \dots, i_k\}\) such that \(i_{j+1} - i_j > 1\) for all \(1 \leq j < k\), and maximize \(\sum_{j=1}^{k} a_{i_j}\). This is a classic dynamic programming problem that can be solved in \(O(n)\) time.

The input is read from standard input and the result should be printed to standard output.

inputFormat

The input consists of two lines:

• The first line contains a single integer \(n\) (where \(0 \leq n \leq 10^5\)) representing the number of elements in the array.
• The second line contains \(n\) space-separated positive integers representing the array elements. If \(n = 0\), the second line will be empty.

outputFormat

Output a single integer representing the maximum sum obtainable by selecting non-adjacent elements from the array.

## sample

5
3 2 5 10 7

15

</p>