Maximum Non-Adjacent Sum

You are given an array of n integers. Your task is to compute the maximum sum possible by selecting a subset of non-adjacent numbers from the array. Formally, if the array is A with elements \(A_1, A_2, \dots, A_n\), you need to maximize the sum \(S = \sum_{i \in I} A_i\) subject to the constraint that for every pair of indices \(i, j \in I\) with \(|i - j| = 1\), at most one is chosen.

Note: If all the numbers in the array are negative or if the array is empty, the maximum sum is defined to be 0.

The problem can be formulated using the recurrence relation:

[ \text{dp}[i] = \max(\text{dp}[i-1], A_i + (i-2 \geq 0 ? \text{dp}[i-2] : 0)) ]

where \(\text{dp}[i]\) represents the maximum non-adjacent sum considering the first \(i+1\) elements. Your solution should read the input from standard input and print the result to standard output.

inputFormat

The first line of input contains a single non-negative integer \(n\) (\(0 \leq n \leq 10^5\)), representing the number of elements in the array. If \(n > 0\), the second line contains \(n\) space-separated integers \(A_1, A_2, \dots, A_n\) (\( -10^9 \leq A_i \leq 10^9\)).

outputFormat

Output a single integer, which is the maximum sum obtainable by selecting a subset of non-adjacent numbers from the array. If the maximum sum is negative, output 0.

5
3 2 5 10 7

15