Maximum Sum of Non-Adjacent Elements

You are given a list of non-negative integers. Your task is to compute the maximum possible sum of a subsequence in which no two elements are adjacent in the original list. More formally, if we denote the list by (a_0, a_1, \dots, a_{n-1}), you need to calculate (f(n)) where: [ f(0) = 0, \quad f(1) = a_0, \quad f(i) = \max(f(i-1), f(i-2) + a_{i-1}) \text{ for } i \ge 2. ] The solution must handle edge cases, such as an empty list, correctly.

inputFormat

The input is read from standard input (stdin) and consists of two lines:

1. The first line contains a single integer (n) representing the number of elements in the array. (n) can be zero.
2. The second line contains (n) space-separated non-negative integers.

If (n = 0), the second line may be empty.

outputFormat

Output a single integer representing the maximum sum of non-adjacent elements, printed to standard output (stdout).## sample

5
3 2 5 10 7

15