Algorithms and Data Structures

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 (1 ≤ ≤ ) the amount you can rob from each house.

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. 1 + 5
  1. 17 + 7 (skip some houses in between)
 

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue