题目描述

小图很喜欢旅游，这次他旅游的国家有 $n$ 个城市，编号依次为 $1$ 到 $n$，并且小图打算从 $1$ 号城市开始按编号依次旅游完所有城市，并且他不会返回已经去过的城市，即每个城市仅走一次。 小图在做旅游攻略时发现，每座城市都有一件相同的纪念品，但是他们的价格可能不一样，所以小图想在某一个城市买入一个纪念品，并在之后的城市中卖掉它，并且小图最少且仅会买入一次卖出一次，这样他就能赚取到其中的差价；于是小图想让你帮他计算一下他最多能赚多少钱，如果亏钱也请告诉他最少亏多少（他只是好奇）。

输入格式

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

第二行有用空格隔开的 $n$ 个整数，第 $i$ 个数字 $a_i$ 表示编号为 $i$ 的城市的纪念品价格。

对于 30% 的测试数据 $2 \leq n \leq 10^3，1 \leq a_i \leq 10^5$；

对于 100% 的测试数据 $2 \leq n \leq 10^6，1 \leq a_i \leq 10^9$。

输出格式

输出一个整数表示小图最多能赚多少钱（亏钱则输出负数）。

样例

5
2 1 6 8 4

7

6
10 8 7 5 3 1

-1