House Robber Problem

You are given a series of houses arranged in a row, where each house has a non-negative integer amount of money.

You need to determine the maximum amount of money you can rob without robbing two adjacent houses. Robbing two consecutive houses will trigger the alarm.

The optimal strategy can be derived using the recurrence relation:

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

Here, nums[i] denotes the money in the i^th house.

inputFormat

The input consists of two lines. The first line contains a single integer n representing the number of houses. 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 is 0, the second line may be empty.

outputFormat

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

4
1 2 3 1

4