问题描述

​ 小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,..a_n$，依次表示小A 要经过的城市的纪念品的价格。

输出格式

输出一个整数， 表示小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≤200000，0< $a_i$ ≤2000000000。