题目描述

你可以很好地预测某只股票未来 N 天的价格。你想从中获利，但每天只需要交易一股股票。也就是说，每天你要么买一股，要么卖一股，要么什么都不做。一开始你拥有零股票，当你没有股票的时候你不能出售股票。在 N 天结束时，你想再次拥有零股票，但想尽可能拥有更多的钱。

输入格式

输入以一个整数 $N(2\leq N\leq 3\cdot10^5)$ 开始，即天数。

接下来的一行恰好有 $N$ 个整数 $p_1, p_2, \dots, p_N (1\leq p_i\leq 10^6)$。$p_i$ 表示一股股票在第 $i$ 天的价格。

输出格式

在 N 天结束时，输出你最终能得到的最大金额。

输入输出样例

9
10 5 4 7 9 12 6 2 10

20

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

41

说明/提示

在第一个例子中，以 5 和 4 的价格分别买入一股，以 9 和 12 的价格分别卖出。 然后在价格为 2 时买入一股，价格为 10 时卖出。 总利润是 -5 - 4 + 9 + 12 - 2 + 10 = 20。