Background

土拨鼠结婚后迷上了炒果子, 他想通过炒"果子"获取更多的收益改变生活, 土拨鼠只能选择 某一天 买入这只果子，并选择在 某一天 卖出该果子。设计一个算法来计算你所能获取的最大利润。

Description

在每一天, 你都可以买入或者卖出果子, 在任何时候你最多只能持有一个果子, 你也可以在今天买入今天卖出. 但是你不可以在没有果子的时候卖出果子. 计算买卖的最大利润.

Format

Input

第1行为n

第2行为n个元素的一个数组 a ，它的第 i 个元素 a[i] 表示果子第 i 天的价格。

Output

你可以从交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

Samples

样例1

6
7 1 5 3 6 4

7

样例2

5
1 2 3 4 5

4

样例解析

样例1解释：在第 2 天（果子价格 = 1）的时候买入，在第 3 天（果子价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。随后，在第 4 天（果子价格 = 3）的时候买入，在第 5 天（果子价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3 。 总利润为 4 + 3 = 7 。

Limitation

1 <= n <= 10^5

0 <= a[i] <= 10^4