Maximum Stock Trading Profit

You are given a sequence of prices representing the price of a stock on consecutive days. Your task is to compute the maximum profit that can be achieved by performing a single buy-and-sell transaction. More formally, given an array (prices) of length (n), you need to find the maximum value of (prices[j] - prices[i]) such that (0 \le i < j < n). If no profit can be achieved, output 0.

Note: You must buy before you sell. If the prices are in descending order or if there is only one price, the maximum profit is 0.

inputFormat

The first line of input contains a single integer (n) representing the number of days. The second line contains (n) space-separated integers representing the stock prices for each day.

outputFormat

Output a single integer representing the maximum profit that can be achieved.## sample

6
7 1 5 3 6 4

5