A row of n houses each holds some amount of money a[i] (which may be negative in this variant). A thief wants to maximise the total money stolen, but cannot rob two adjacent houses (indices i and i+1 may not both be chosen).
The thief may also choose to rob no house at all, in which case the loot is 0. Return the maximum total loot.
Formally: choose a subset S of indices with no two consecutive indices such that sum(a[i] for i in S) is maximised; the empty subset (sum 0) is allowed.
Input format
Line 1: a single integer n (the number of houses).
Line 2: n space-separated integers a[0] a[1] ... a[n-1]. This line is absent when n = 0.
Output format
A single line containing one integer: the maximum non-adjacent sum (at least 0, since the empty selection is allowed).
Constraints
- 0 ≤ n ≤ 100000
- -10^9 ≤ a[i] ≤ 10^9
Example
For a = [2, 7, 9, 3, 1] the best is to take houses 0, 2, 4 (2 + 9 + 1 = 12).