Skip to content

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了,可以的话,请您参考添加页面,与大家一起分享你的题解!