A share has a known price on each of n days. You may complete any number of buy-then-sell trades, holding at most one share at a time, with one extra rule: after you sell on a day, you must skip the next day (you cannot buy on the day immediately following a sale). Buying and selling happen on distinct days.
Return the maximum total profit. Doing nothing yields 0.
Input format
Line 1: an integer n, the number of days.
Line 2: n space-separated non-negative integers, the daily prices (present whenever n >= 1).
Output format
A single integer: the maximum achievable profit under the one-day cooldown rule.
Constraints
- 1 <= n <= 100000
- 0 <= price <= 1000000000