Maximum Non-Adjacent Subsequence Sum

Given an array of integers, your task is to compute the maximum sum of a subsequence such that no two selected elements are adjacent in the original array. Specifically, if you choose an element at index i, you cannot choose any element at index i-1 or i+1. Formally, if indices i and j are chosen then they must satisfy $|i - j| \neq 1$. Note that if all array elements are negative, the result should be 0 (i.e., choose an empty subsequence).

inputFormat

The first line contains a single integer n (1 ≤ n ≤ 10^5) indicating the number of elements in the array. The second line contains n space-separated integers representing the elements of the array.

outputFormat

Output a single integer—the maximum sum of a subsequence with the property that no two chosen numbers are adjacent in the original array.## sample

5
3 2 5 10 7

15