D. 低买高卖（Buy Low Sell High）

题目描述

你能够准确预测某只股票未来 N 天的价格。

你希望利用这些信息尽可能多地获利，但每天最多只能进行一次股票操作。也就是说，每一天你只能选择以下三种操作之一：

• 买入 1 股股票；
• 卖出 1 股股票；
• 什么都不做。

初始时，你持有 0 股股票。

当你没有持有任何股票时，不能进行卖出操作。

在第 N 天结束后，你要求自己再次持有 0 股股票，同时希望最终获得的利润尽可能大。

请你计算最大可能利润。

---

输入格式

第一行输入一个整数 N，表示天数。

2 ≤ N ≤ 3 × 10^5

第二行输入 N 个整数：

p1, p2, ..., pN

其中 pi 表示第 i 天一股股票的价格。

1 ≤ pi ≤ 10^6

---

输出格式

输出一个整数，表示在第 N 天结束时，能够获得的最大利润。

---

样例 1

输入

9
10 5 4 7 9 12 6 2 10

输出

20

样例解释

股票价格依次为：

10 5 4 7 9 12 6 2 10

一种最优操作方案为：

• 价格为 5 时买入 1 股；
• 价格为 4 时再买入 1 股；
• 价格为 9 时卖出 1 股；
• 价格为 12 时再卖出 1 股；
• 价格为 2 时买入 1 股；
• 价格为 10 时卖出 1 股。

最终利润为：

-5 - 4 + 9 + 12 - 2 + 10 = 20

因此最大利润为：

20

---

样例 2

输入

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

输出

41

---

注意

这道题与“只能同时持有一股股票”的经典股票题不同。

本题允许你同时持有多股股票。例如，你可以连续几天每天买入 1 股，之后再连续几天每天卖出 1 股。

唯一的限制是：

每天最多只能买入或卖出 1 股。

并且最终必须把所有股票全部卖出，也就是结束时持股数量必须为 0。