Maximum Non-Adjacent Subset Sum

Given an array of integers, find the maximum sum that can be obtained by selecting a subsequence of the array such that no two elements in the subsequence are adjacent in the original array. Note that if all numbers are negative, the answer is 0 (i.e., you may choose an empty subsequence).

Constraint: The subsequence can be empty, and the maximum sum is defined as the greatest sum achievable under the given restriction.

For example, consider the array [3, 7, 4, 6, 5]. One optimal subsequence is [3, 4, 5] which sums up to 12, but the best possible is [7, 6] which gives 13.

The solution should read input from standard input and write the result to standard output.

inputFormat

The input consists of two lines:

• The first line contains a single integer n (1 ≤ n ≤ 10⁵) — the number of elements in the array.
• The second line contains n space-separated integers, which can be positive, negative or zero.

outputFormat

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

## sample

5
3 7 4 6 5

13

</p>