Maximum Non‐Adjacent Sum

You are given an array of integers. Your task is to determine the maximum sum you can obtain by summing a subset of these integers such that no two numbers in the subset are adjacent in the original array.

For example, given the array [3, 2, 5, 10, 7], one optimal selection would be 3, 5, and 7 which gives a total sum of 15, since selecting 10 would force you to skip both 5 and 7.

Note: If the array is empty, the answer is 0.

The goal is to implement a solution that reads the input from the standard input (stdin) and outputs the result to the standard output (stdout).

inputFormat

The first line of input contains an integer n (0 ≤ n ≤ 10^5) representing the number of elements in the array. The second line contains n space‐separated integers which represent the elements of the array. If n is 0, then the second line may be omitted.

outputFormat

Output a single integer which is the maximum sum of non-adjacent elements that can be obtained from the array.

5
3 2 5 10 7

15