Best day to buy and sell

Problem

Share prices are listed day by day. You may buy on one day and sell on a later day. Print the largest profit possible, or 0 if the prices only fall.

Example 1

Input

6
7 1 5 3 6 4

Output

Buy at 1, sell at 6: profit 5.

Example 2

Input

5
7 6 4 3 1

Output

Prices only fall.

Try the problem first. Open one hint at a time.

Hint 1

Remember the lowest price seen so far.

Hint 2

At each day, the best profit that sells today is today's price minus that lowest price.

Write your Python code, run it on the examples and submit it to hidden tests.