You are planning to rob houses on a street. There are
nhouses and you know the amount of money you can rob from each of those. The alarm system automatically contacts the police if two adjacent houses are robbed on the same night.
What would be the maximum possible amount you could get during one night without getting caught?
The first line of the input contains a single integer
n(1 ≤ n ≤ ).
The next line contains
(1 ≤ ≤ ) the amount you can rob from each house.
The program should print the maximum possible amount you could get without getting caught.
4 1 2 5 1
5 3 17 12 3 7
- 1 + 5
- 17 + 7 (skip some houses in between)
Time limit: 1 seconds
Memory limit: 512 MB
Output limit: 1 MB