题目描述

小 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 最多能赚多少钱（当然也有可能亏钱）？

输入格式

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

第二行，~n~ 个用一个空格隔开的正整数，~a_1,a_2,\ldots,a_n~，依次表示小 A 要经过的城市的纪念品的价格。

输出格式

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

输入输出样例 #1

输入 #1

5
2 1 6 8 4

输出 #1

7

输入输出样例 #2

输入 #2

6
10 8 7 5 3 1

输出 #2

-1

说明/提示

对于 ~30\%~ 的数据：~n\le 1000~。

对于 ~100\%~ 的数据：~2\le n\le 2\times 10^5~，~0< a_i\le 2\times 10^9~。