Maximum Sum of Non-Adjacent Elements

You are given an array of integers. Your task is to compute the maximum sum of a subsequence with the constraint that no two elements in the subsequence are adjacent in the original array.

Formally, let the array be \( A = [a_1, a_2, \dots, a_n] \). You need to select a subset of indices \( \{ i_1, i_2, \dots, i_k \} \) such that for any two consecutive indices \( i_j \) and \( i_{j+1} \), \( i_{j+1} - i_j \ge 2 \). The goal is to maximize the sum \( \sum_{j=1}^{k} a_{i_j} \). If the array is empty, the answer is 0.

Input/Output: The input is read from standard input (stdin) and the output should be written to standard output (stdout).

inputFormat

The first line of input contains a single integer \( n \) representing the number of elements in the array. The second line contains \( n \) space-separated integers representing the array \( A \).

If \( n = 0 \), then there will be no second line.

outputFormat

Output a single integer which is the maximum sum of non-adjacent elements in the given array.

4
3 2 7 10

13