Robbing houses
You are planning to rob houses on a street. There are
n houses 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?
Input
The first line of the input contains a single integer
n (1 ≤ n ≤ ).The next line contains
n space-separated integers Output
The program should print the maximum possible amount you could get without getting caught.
Examples
Input | Output |
4
1 2 5 1 | 6 |
5
3 17 12 3 7 | 24 |
Explanation
- 1 + 5
- 17 + 7 (skip some houses in between)
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB