House Robber Problem

You are given a row of \( n \) houses, each with some amount of money represented by an array \( a \). Due to security systems, you cannot rob two adjacent houses on the same night. Your task is to compute the maximum amount of money you can rob without alerting the police.

The problem can be solved using dynamic programming with the recurrence:

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

where \( dp[i] \) represents the maximum money robbed from the first i+1 houses.

inputFormat

The input is given via stdin. The first line contains an integer ( n ) (( n \geq 0 )) representing the number of houses. The second line contains ( n ) space-separated integers where the ( i^{th} ) integer represents the amount of money in the ( i^{th} ) house. If ( n = 0 ), the second line will be empty.

outputFormat

Output a single integer to stdout representing the maximum amount of money that can be robbed without alerting the police.## sample

4
1 2 3 1

4