House Robber Problem

Given a sequence of non-negative integers representing the amount of money in each house, determine the maximum total amount that can be robbed without alerting the police. The police will be alerted if two adjacent houses are robbed on the same night.

We can solve this problem using dynamic programming. Let (dp[i]) denote the maximum amount of money that can be robbed from the first (i+1) houses. Then, for (i \ge 2), the recurrence is given by:
$$dp[i] = \max(dp[i-1],, dp[i-2] + nums[i])$$
where (nums[i]) is the amount of money in the (i)-th house.

For example, if the houses contain the amounts [2, 7, 9, 3, 1], then the maximum amount that can be robbed is 12.

inputFormat

The input is read from standard input. The first line contains a single integer (n) indicating the number of houses. If (n > 0), the second line contains (n) non-negative integers separated by spaces, where the (i)-th integer represents the amount of money in the (i)-th house. If (n = 0), no second line is provided.

outputFormat

Output a single line that contains one integer: the maximum amount of money that can be robbed without robbing two adjacent houses.## sample

4
1 2 3 1

4