Maximum Chocolates Stolen

You are given n houses in a row, where the i^th house contains a certain number of chocolates. A thief wants to steal chocolates from these houses subject to the constraint that he cannot steal from two consecutive houses. Your task is to determine the maximum number of chocolates the thief can steal.

The problem can be formalized using dynamic programming. Let \(dp[i]\) represent the maximum amount of chocolates that can be stolen from the first \(i+1\) houses. The recurrence relation is given by:

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

with the initial conditions:

[ dp[0] = chocolates[0],\quad dp[1] = \max(chocolates[0], chocolates[1]) ]

Your goal is to compute \(dp[n-1]\) based on the input list of chocolates.

inputFormat

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

• The first line contains a single integer \(n\) representing the number of houses.
• The second line contains \(n\) integers separated by spaces, where the \(i^th\) integer represents the number of chocolates in the \(i^th\) house. If \(n = 0\), the second line may be empty.

outputFormat

Output a single integer, the maximum number of chocolates that can be stolen, to standard output.

## sample

5
3 2 7 10 12

22