House Robber

Problem statement

A planner selects storage lockers along one corridor. Each locker has a nonnegative reward, but two neighbouring lockers cannot both be selected. Find the greatest total reward possible. Selecting no lockers is allowed.

Input format

First line: n. Second line: n space-separated integers.

Output format

Print the maximum total reward.

Constraints

1 <= n <= 100000; 0 <= reward <= 10000; use 64-bit arithmetic for totals.

Sample input

5
4 1 2 9 3

Sample output

13