该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

你有预测股票的能力：可以知道某只股票未来 $\red{N}$天的价格。 你当然准备通过这项能力获利，但为了不让别人发现你的"钞能力"，只打算每天最多交易一股股票。也 就是说，每天你要么买入一股，要么卖出一股（当你没有任何股票时，你就不能出售），要么什么都不 做。

最初你拥有零股，但可以融资（借钱）。在 $\red{N}$天结束后，你要把借来的钱还回去，同时帐下恢复零股。

现在问题来了：通过最合理的买卖，你可以从这 $\red{N}$天内赚到多少钱。

输入格式

第一行输入一个数，表示 $\red{N}$。

接下来一行是$\red{N }$个数， $\red{p_i}$表示股票在第 $\red{i}$天的价格。

输出格式

输出一个数$\red{M ，}$表示这 $\red{N}$天最多可以赚到的利润。

样例

输入样例1

9
10 5 4 7 9 12 6 2 10

输出样例1

20

输入样例2

20
3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3 2 3 8 4

输出样例2

41

提示

对于前 $\red{20\%}$的数据，$\red{N<=1000 }$；

对于$\red{20\% \sim 30\% }$的数据，$\red{1<=p_i<=2 }$；

对于 $\red{100\%}$的数据，$\red{N<=100000 ，}$$\red{1<=p_i<=1000000 }$。