题目描述

你可以完美预测某只股票未来 $N$ 天的价格。你希望利用这一信息获利，但每天只能进行一次交易：买入一股、卖出一股，或者什么都不做。初始时你持有 $0$ 股，不允许在手中没有股票时卖出。在 $N$ 天结束时，你希望手中再次持有 $0$ 股，并希望最终获得的利润尽可能大。

输入格式

第一行包含一个整数 $N$，表示天数。

第二行包含 $N$ 个整数 $p_1, p_2, \dots, p_N$，$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$。

数据范围与提示

• $2 \le N \le 3 \times 10^5$
• $1 \le p_i \le 10^6$
• 时间限制：$2$ 秒
• 内存限制：$256$ MB