Maximum Profit

You are given the prices of a stock over n consecutive days. Your task is to compute the maximum profit that can be achieved by making a single buy-sell transaction. In other words, you need to choose a day to buy and a later day to sell in order to maximize the profit.

The profit from buying on day i and selling on day j is given by: $$Profit = P_j - P_i, \quad \text{where } j > i.$$ If no profit can be made, the answer should be 0.

Note: You are only allowed to complete one transaction (i.e., buy one and sell one share of the stock) and you must buy before you sell.

inputFormat

The input is given via standard input and consists of two lines:

• The first line contains a single integer n representing the number of days.
• The second line contains n space-separated integers where the i^th integer is the price of the stock on day i.

outputFormat

Output a single integer, the maximum profit obtainable from a single buy-sell transaction. If no profit is possible, output 0.

6
7 1 5 3 6 4

5