You are given an array of prices, where pricesi contains the price of a stock on the i-th day.
You want to maximize your profit by selecting one day to buy one stock and choosing another day in the future to sell that stock.
Find the maximum profit that can be obtained from this transaction.
The first line contains the size n (n≤105) of the price array. The second line contains the array of prices — n integers, each not exceeding 104.
Print the maximum profit that can be obtained from one transaction. If it is impossible to obtain profit, print 0.