A street has n billboard slots in a row. Slot i yields net revenue v_i if rented (this can be negative, if upkeep exceeds income). Zoning rules forbid renting two directly adjacent slots (slot i and slot i+1 cannot both be rented). Choose a subset of slots (possibly none) to maximize total net revenue.
Input format
Line 1: an integer n.
Line 2: n space-separated integers v_1 ... v_n (empty if n = 0).
Output format
A single integer: the maximum total revenue achievable (renting no slots, for a total of 0, is always allowed).
Constraints
- 0 ≤ n ≤ 100000
- -1000 ≤ v_i ≤ 1000