Best Time to Buy and Sell Stock

You are given an array of prices, where $price{s}_i$ 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.

Input

The first line contains the size $n(n\le 10^5)$ of the price array. The second line contains the array of prices — $n$ integers, each not exceeding $10^4$.

Output

Print the maximum profit that can be obtained from one transaction. If it is impossible to obtain profit, print $0$.

Examples