Max Non-Adjacent Subsequence Sum

In this problem, you are given a sequence of integers (a_1, a_2, \ldots, a_n). Your task is to compute the maximum sum of a non-empty subsequence such that no two elements in the subsequence are adjacent in the original sequence. Formally, if you choose indices (i_1, i_2, \ldots, i_k) with (1 \leq i_1 < i_2 < \cdots < i_k \leq n) and (i_{j+1} - i_j \ge 2) for all (1 \leq j < k), then the goal is to maximize (\sum_{j=1}^k a_{i_j}).

Note:\n- The sequence can contain both positive and negative integers.\n- In case all integers are negative, the answer is the maximum (i.e. the least negative) element.

inputFormat

The input is read from standard input (stdin) and consists of two lines:\n\nThe first line contains an integer (n) ((1 \le n \le 10^5)) representing the number of elements.\nThe second line contains (n) space-separated integers representing the sequence (a_1, a_2, \ldots, a_n).

outputFormat

Output a single integer to standard output (stdout): the maximum sum of a non-empty subsequence with no two adjacent elements taken from the original sequence.## sample

5
3 2 5 10 7

15