Maximum Sum of Non-Adjacent Subsequence

You are given an array of integers and you need to compute the maximum sum of a subsequence such that no two elements in the subsequence are adjacent in the original array. In other words, if the array is (A = [a_1, a_2, \dots, a_n]), you must choose a subset (I \subseteq {1,2,\dots,n}) with the constraint that if (i \in I) then (i+1 \notin I). Your task is to find (\max_{I}\sum_{i \in I}a_i).

inputFormat

The input is given via standard input (stdin). The first line contains a single integer (n) which represents the number of elements in the array. The second line contains (n) space-separated integers representing the elements of the array. If (n = 0), then the array is empty.

outputFormat

Output a single integer to standard output (stdout): the maximum sum of a subsequence with the constraint that no two selected elements are consecutive in the original array.## sample

4
3 2 7 10

13