Best Time to Buy and Sell Stock

Problem statement

A campus shop tracks the daily cost of a reusable equipment token. It may buy one token and sell it on a later day. Find the largest possible profit from that single trade. The shop may skip trading, yielding zero profit.

Input format

First line: n. Second line: n space-separated integers.

Output format

Print the maximum profit.

Constraints

1 <= n <= 100000; 0 <= price <= 1000000000.

Sample input

6
9 3 8 2 7 4

Sample output

5