An assembly line produces n units in order; unit i yields an integer profit a[i] (a defect gives a negative profit). You pick a non-empty contiguous run of units and may discard at most one unit from within that run to improve its total. After discarding, at least one unit must remain. Report the maximum achievable total profit.
Discarding is optional: if keeping the whole run is best, you keep it. You may not discard more than one unit, and you may not discard from a run of length 1 (nothing would remain).
Input format
Line 1: an integer n.
Line 2: n space-separated integers, the per-unit profits in order.
Output format
A single integer: the maximum total profit of a non-empty contiguous run after at most one optional deletion.
Constraints
- 1 <= n <= 100000
- -1000000 <= each profit <= 1000000