Given `n` integers that represent the stock prices of your favorite company, youβd like to decide what would be the best time to buy and sell the stock. You would like to buy the stock only once and sell it only once. So, youβd like to maximize the profit (buy low and sell high).
Determine the maximum possible profit you can make on your favorite company, and if there is no way to do so, you should print 0 (meaning you wonβt buy or sell that stock).

#### Input

The first line of the input contains a single integer `n` (1 β€ n β€
).
The next line contains space-separated integers
representing the prices of the stock (0 β€
β€ 1000).

#### Output

The program should print the maximum possible profit you can make on buying and selling your favorite stock.

#### Examples

 Input Output 5 4 2 6 8 1 6 4 8 6 4 3 0

#### Explanation

1. We buy when the stock value is 2 and we sell it when itβs 8
1. We wonβt be able to make any profit as the stock value constantly declines
Β
Hint
At each point, you can keep a state of the current βbestβ possible answer and another value for the cheapest the stock has ever been.
Β

#### Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB