Maximum Gold Collection

You are given an array \( A \) of size \( N \), where each element represents the number of gold coins in a chest. The goal is to collect the maximum amount of gold without ever taking coins from two consecutive chests.

Problem Explanation: You cannot collect from adjacent chests. Thus, if you pick coins from the \( i^{th} \) chest, you must skip the \( (i+1)^{th} \) chest. This is a classical dynamic programming problem where the recurrence can be formulated as:

\( dp[i] = \max(dp[i-1], dp[i-2] + A[i]) \)

with base cases \( dp[0] = A[0] \) and \( dp[1] = \max(A[0], A[1]) \). If \( N = 0 \), the answer is 0.

inputFormat

The first line of input contains an integer \( N \) representing the number of chests.

The second line contains \( N \) space-separated integers, where each integer \( A[i] \) represents the amount of gold coins in the \( i^{th} \) chest. If \( N = 0 \), the second line may be omitted.

outputFormat

Output a single integer which is the maximum amount of gold coins that can be collected under the given restriction.

## sample

4
5 3 4 11

16

</p>