题目描述

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

小博很聪明，在没出发之前，他已经了解到，每个城市都有他喜欢的小熊纪念品，但是每个城市的价格可能不一样（但是在同一个城市买入和卖出一个小熊纪念品的价格相同），于是小博打算从经过的某一个城市$x$买一个纪念品，然后在后面的第某个城市$y$卖掉，从而赚取其中的差价。

请注意：他必须在某个城市买$1$次，而且只能买$1$个，并且一定要在后面的某个城市卖掉（不能在同一个城市先买入后再卖出），因为他家里已经有很多小熊纪念品了，小博希望赚的钱越多越好。 问：小博最多能赚多少钱？(当然也有可能亏钱）

输入格式

第一行，一个整数$n$，表示城市的个数。 第二行，$n$个用一个空格隔开的正整数，$a_1,a_2...a_n$，依次表示小博经过的每一个城市的纪念品价格。

输出格式

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

样例

5
2 1 6 8 4

7

6
10 8 7 5 3 1

-1

数据范围

$30\%$的数据满足，$n\le 1000$

$100\%$的数据满足，$2\le n \le 200000，0\le a_i \le 2\times 10^9$

样例解释

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

样例2中，在$2$号城市花$8$元买，在$3$号城市$7$元卖掉，赚$-1$元。