Maximizing Souvenir Profit

Little A loves to travel. His country has n cities numbered from 1 to n. This summer, he plans to visit all cities in increasing order starting from city 1 and ending at city n, without backtracking (each city is visited exactly once).

Every city has a bear souvenir that Little A likes, but the prices vary between cities. Before departing, he learns that at each city the price for buying and selling the souvenir is the same. He intends to make a single transaction: buy one souvenir in one city x and then later sell it in some city y (with y > x). Note that buying and selling in the same city is not allowed. His goal is to maximize his profit (which might also be negative if the selling price is lower than the purchase price).

For example, if the souvenir prices in cities 2, 6, and 10 are 10, 8, and 18 respectively: buying in city 2 for 10 and selling in city 6 for 8 yields a profit of -2 while selling in city 10 for 18 yields a profit of 8.

Determine the maximum profit Little A can obtain.

The profit is mathematically represented as:

\[ \text{Profit} = P_y - P_x \quad (1 \leq x < y \leq n), \]

where \(P_i\) denotes the souvenir price in city \(i\). You need to compute the maximum value of \(P_y - P_x\) for the given sequence.

inputFormat

The first line contains a single integer n (the number of cities). The second line contains n space-separated integers, where the i-th integer represents the price of the souvenir in the i-th city.

outputFormat

Output a single integer, which is the maximum profit that Little A can achieve by buying one souvenir and selling it later. Note that the result may be negative if little A is forced to incur a loss.

sample

5
3 1 4 8 7

7