1433: Bo

题目

题目描述

博先生掌握了股市内幕消息，因此他想闷声大发财。

对于特定的一只股票，博先生知道了他 $n$ 天内的价格走势，并想借此牟利。但是，如果一次交易太多的被发现的话，人生就要结束了罢。因此，他每天只能做以下三种操作之一：

• 以当天的价格买入一股。
• 以当天的价格卖出一股。博先生不能在持有 $0$ 股时卖出。
• 或者，什么也不做。

博先生现在持有 $0$ 股股票，他希望在第 $n$ 天结束时手里持有 $0$ 股股票。请帮博先生计算一下，他最多能赚多少钱？

Input

请从 stdin 读入。

第一行一个正整数 $n (1 \leq n \leq 10 ^ 5)$ 表示总天数。

第二行 $n$ 个空格隔开的正整数，第 $i$ 个为第 $i$ 天的价格 $a_i (1 \leq a_i \leq 10^6)$。

对于 $20$ 分的数据，$n \leq 10$。

另有 $20$ 分的数据，$n \leq 500$。

Output

请输出到 stdout 中。

对于每组数据输出一行一个整数，表示答案。

Sample Input

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

Sample Output

0 20 41

Note

对于第一组数据，由于这只股票实在太烂了，因此最优方案是：快跑。

对于第二组数据，最优的交易是：$-5 -4+9+12-2+10 = 20$。

Constraints

Time Limit: 1s

Memory Limit: 128MB

Oops! 本题目还没有解答！

助教老师们编题的速度，已经超过了解题的速度！

OJ翻了一新，但本解答集还大多用的是2017-2019级，甚至更早的同学们贡献的答案。

如果你已经AC了，可以的话，请您参考添加页面，与大家一起分享你的题解！