Maximum Sum of Non-Adjacent Elements

Given an array of integers, your task is to calculate the maximum sum of a subsequence such that no two elements in the subsequence are adjacent in the original array. This is a classic dynamic programming problem.

In this problem, you are provided an integer n indicating the number of elements in the array, followed by a line containing n space-separated integers. Your goal is to select elements in a way that no two selected numbers are next to each other in the original order, and the sum of these selected numbers is maximized.

Formally, if the array is (a_1, a_2, \dots, a_n), you need to choose a subset of indices (I) such that if (i \in I), then (i+1 \notin I), and maximize (\sum_{i \in I} a_i).

inputFormat

The input is read from standard input (stdin) and has the following format:

The first line contains an integer (n) representing the number of elements in the array.
The second line contains (n) space-separated integers, each representing an element of the array.

Note: If (n = 0), the array is empty.

outputFormat

Output a single integer to standard output (stdout), which is the maximum sum of non-adjacent elements that can be obtained from the array.## sample

5
3 2 5 10 7

15