Description

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

Format

Input

第一行一个整数 $n(1 \leq n \leq 10^6)$，表示城市的数量。第二行有用空格隔开的 $n$ 个整数，第 $i$ 个数字 $a_i(1 \leq a_i \leq 10^9)$ 表示编号为 $i$ 的城市的纪念品价格。

Output

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

Samples

5
2 1 6 8 4

7

6
10 8 7 5 3 1

-1

Hint