House Robber Problem

You are given n houses arranged in a row, and each house contains some amount of money. A thief wants to maximize the amount of money stolen without alerting the police by robbing two adjacent houses.

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

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

with the boundary conditions:

[ dp[0] = money[0] \quad\text{and}\quad dp[1] = \max(money[0], money[1]). ]

Your task is to implement this logic.

inputFormat

The input is provided via standard input (stdin). The first line contains an integer (n), representing the number of houses. The second line contains (n) space-separated integers, where the (i)-th number represents the amount of money in the (i)-th house. If (n = 0), the second line is omitted.

outputFormat

Output a single integer denoting the maximum amount of money that can be stolen, printed to standard output (stdout).## sample

4
1 2 9 4

10