Best single trade

Problem

Given the price of a share on each day, you may buy once and sell once on a later day. Print the largest profit. If no trade makes a profit, print 0.

Example 1

Input

7 1 5 3 6 4

Output

Example 2

Input

7 6 4 3 1

Output

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

Hint 1

You need the lowest price before each day.

Hint 2

Keep the lowest price so far and the best difference so far in one pass.

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