【题目描述】

小 A 很喜欢旅游，他的国家共有 n 个城市，编号依次为 1 到 n，这个暑假小 A 打算从 1 号 城市开始按编号从小到大依次旅游完所有的城市，最后达到 n 号城市，而且他不走回头路， 每个城市只走一次。

小 A 很聪明，在没出发之前，他已经了解到，每个城市都有他喜欢的小熊纪念品，但是 每个城市的价格却不完全一样（在同一个城市买入和卖出一个小熊纪念品的价格相同），于是 小 A 打算从经过的某一个城市 x 买一个纪念品，然后在后面经过的某个城市 y 卖掉，从而赚 取其中的差价。但是他必须在某个城市买 1 次，而且只能买 1 个，并且一定要在后面的某个 城市卖掉（不能在同一个城市先买入后再卖出），因为他家里已经有很多小熊纪念品了。

如，2 号城市的纪念品价格是 10 元，6 号城市的纪念品是 8 元，10 号城市的纪念品是 18 元，假设小 A 在 2 号城市花 10 元钱买了一个纪念品，如果在 6 号城市卖掉他就亏了 2 元（赚 -2 元），如果在 10 号城市卖，他就会赚 8 元。 小 A 希望赚的钱越多越好。

问：小 A 最多能赚多少钱（当然也有可能亏钱）？

【输入格式】

输入文件 money.in。

第一行一个整数 n，表示城市的个数。

第二行，n 个用一个空格隔开的正整数，a1,a2,..an，依次表示小 A 要经过的城市的纪念 品的价格。

【输出格式】

输出文件 money.out

输出一个整数，表示小 A 能赚到钱的最大值。

【样例 1 输入】

5
2 1 6 8 4

【样例 1 输出】

7

【样例 1 解释】

在 2 号城市花 1 元买，在 4 号城市 8 元卖掉，赚 7 元。

【样例 2 输入】

6
10 8 7 5 3 1

【样例 2 输出】

-1

【样例 2 解释】

在 2 号城市花 8 元买，在 3 号城市 7 元卖掉，赚-1 元，即亏了 1 元。

【数据范围】

• 30%的数据：$n≤1000$。
• 100%的数据：$2≤n≤2 \times 10^5, 0 \lt a_i \le 2 \times 10^9$。