Maximum Subset Sum without Adjacent Elements

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

The problem can be described by the recurrence relation: \[ F(i) = \max\big(F(i-1), a_i + F(i-2)\big) \] with the initial conditions \(F(0)=a_0\) and \(F(1)=\max(a_0, a_1)\). If the array is empty, the answer is 0.

Implement a solution that reads input from standard input and writes the result to standard output.

inputFormat

The first line contains an integer \(N\) representing the number of elements in the array. The second line contains \(N\) space-separated integers representing the array.

outputFormat

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

6
3 2 5 10 7 1

15