说明

本题必须使用文件重定向，输入文件名money.in，输出文件名money.out

题目描述

小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能赚到钱的最大值。

样例

5
2 1 6 8 4

7

样例1解释

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

6
10 8 7 5 3 1

-1

样例2解释

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

数据范围

• 30%的数据:$n≤1000$
• 100%的数据:$2≤n≤200000，0<a_i≤2000000000$

来源

山东CSP-X2023 小学组复赛