Bitcoin investment

Bitcoin is a digital asset and a payment system published under the name Satoshi Nakamoto. Nobody knows whether that name is real or a pseudonym, or whether it belongs to one person or to a group.

The price of one bitcoin in euros moves fast. It can cost 800 euros one day and 20 euros two days later.

Suppose you know every future exchange rate from bitcoin to euros and you want the largest gain you can get. You hold no bitcoin at the start. You buy exactly one bitcoin on some day and sell it on the same day or on a later day. Your gain is the selling price minus the buying price.

Here is a worked case. The price of one bitcoin over the next 10 days is:

Buying on day 1 for 5 euros and selling on day 2 for 11 euros gains 6 euros. Buying on day 4 for 2 euros and selling on day 6 for 10 euros gains 8 euros, and 8 euros is the largest gain these prices allow.

Given the list of exchange rates, compute the largest gain. You buy once and sell once, and the selling day is never earlier than the buying day. Buying and selling on the same day gains 0, so the answer is never negative.

The first line contains an integer $n$, the number of exchange rates ($1 \le n \le 100000$).

The second line contains $n$ integers, the price of one bitcoin in euros on each of the $n$ days. Every price is between 1 and 10000.

Print the largest gain you can obtain.