← 返回题目列表

Codeforces · 865/D

D. 低买高卖

中文机器翻译题面 查看原题

您可以完美预测某只股票未来N天的价格。您想利用这些知识获利,但只想每天交易一股股票。也就是说,每天您要么买入一股,卖出一股,要么什么也不做。最初您拥有零股,当您没有任何股票时,您不能出售股票。在 N 天结束时,您想再次拥有零股,但希望拥有尽可能多的钱。

输入

输入以整数 N (2 ≤ N ≤ 3·105) 开头,即天数。

接下来是一行恰好包含 N 个整数 p1, p2, ..., pN (1 ≤ pi ≤ 106)。第 i 天一股股票的价格由 pi 给出。

输出

打印 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

注意

在第一个示例中,以 5 买入一股,以 4 买入另一股,以 9 卖出一股,以 12 卖出另一股。然后以 2 买入并以 10 卖出。总利润为 - 5 - 4 + 9 + 12 - 2 + 10 = 20。