House Robber Problem

You are given a list of non-negative integers where each integer represents the amount of money at a house. Adjacent houses cannot be robbed together because it would alert the police. Your task is to determine the maximum amount of money you can rob without alerting the police.

This problem should be solved using dynamic programming with O(1) extra space.

inputFormat

The first line of input contains an integer n, the number of houses. The second line contains n space-separated non-negative integers representing the amount of money at each house.

outputFormat

Output a single integer representing the maximum amount of money that can be robbed without triggering the alarm.## sample

1
5

5