You are given n values in a row. You may select any subset of them (possibly none), subject to one rule: you may never select three CONSECUTIVE values (selecting two in a row is fine, but not three). Maximize the total sum of the selected values (values may be negative).
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 achievable sum (selecting nothing, for a total of 0, is always allowed).
Constraints
- 0 ≤ n ≤ 100000
- -1000 ≤ v_i ≤ 1000