A single share of a stock has a known price on each of n consecutive trading days. You may buy the share on one day and sell it on a strictly later day, at most once. If no purchase-then-sale earns a positive profit, you simply do not trade.
Return the maximum profit you can make.
Input format
Line 1: an integer n, the number of days.
Line 2: n space-separated non-negative integers, the price on each day (present whenever n >= 1).
Output format
A single integer: the maximum achievable profit, or 0 if every possible sale would lose money or break even.
Constraints
- 1 <= n <= 100000
- 0 <= price <= 1000000000
- The buy day must come strictly before the sell day.