您可以完美预测某只股票未来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。