题目描述

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

每个城市都有小 A 喜欢的小熊纪念品，但不同城市的价格不完全一样；在同一城市买入、卖出一个纪念品的价格相同。小 A 必须在某个城市买一个纪念品，而且只能买一次、只买一个，再在后面经过的某个城市卖掉。不能在同一个城市先买入再卖出。

例如，在价格为 $10$ 元的城市买入，随后在价格为 $8$ 元的城市卖出，利润为 $-2$ 元；若随后在价格为 $18$ 元的城市卖出，利润为 $8$ 元。

请计算小 A 最多能赚多少钱，结果可能为负数。

输入格式

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

第二行 $n$ 个用空格隔开的正整数 $a_1,a_2,\ldots,a_n$，依次表示各城市纪念品价格。

输出格式

输出一个整数，表示一次合法交易的最大利润。

5
2 1 6 8 4

7

6
10 8 7 5 3 1

-1

说明与数据范围

样例1：在2号城市花1元买入，在4号城市以8元卖出，赚7元。

样例2：在2号城市花8元买入，在3号城市以7元卖出，利润为-1元。

30%的数据：$n\le1000$。

100%的数据：$2\le n\le200000$，$0<a_i\le2000000000$。