A share has a known price on each of n consecutive days. You may buy and sell as many times as you like, but you may hold at most one share at a time: you must sell the share you hold before buying again. Buying and selling on the same day is not allowed (a sale happens on a later day than its buy).
Return the maximum total profit over the whole period.
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 total profit achievable, or 0 if no profit is possible.
Constraints
- 1 <= n <= 100000
- 0 <= price <= 1000000000