Maximum Money Collection

You are given an integer N representing the number of positions and an array of N integers where each integer represents the amount of money at that position. Your task is to compute the maximum amount of money that can be collected under the constraint that you cannot collect money from adjacent positions. In other words, if you collect money at position i, you cannot collect money from position i-1 or i+1.

The problem can be solved using dynamic programming. Let \(dp[i]\) denote the maximum amount of money that can be collected up to the \(i^{th}\) position. The recurrence relation is given by:

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

with the base cases:

• \(dp[0] = money[0]\)
• \(dp[1] = \max(money[0], money[1])\) (if \(N \geq 2\))

Your solution should read from standard input (stdin) and write to standard output (stdout).

inputFormat

The input is read from standard input (stdin) and consists of two lines:

1. First line: A single integer N representing the number of positions.
2. Second line: N space-separated integers indicating the amount of money at each position.

outputFormat

Output a single integer which is the maximum amount of money that can be collected while obeying the constraint of not collecting from adjacent positions.

## sample

4
1 2 3 1

4