题目描述

你可以完美地预测某只股票接下来 $N$ 天的价格，你想利用这一知识盈利，但你每天只想买卖一股，这表明你每天要么什么都不干，要么买入一股，要么卖出一股。起初你没有股票，你也不能在没有股票时卖出股票。你希望在第 $N$ 天结束时不持有股票，并最大化盈利。

输入格式

第一行一个整数 $N$（$2 \le N \le 3 \times 10^5$），表示天数。

接下来一行 $N$ 个整数 $p_1,p_2,\dots p_N$（$1 \le p_i \le 10^6$），表示第 $i$ 天的股价。

输出格式

输出你第 $N$ 天结束时的最大盈利。

样例解释

在股价为 $5,4$ 时各买入一股，在股价为 $9,12$ 时各卖出一股，接着在股价为 $2$ 时买入一股，股价为 $10$ 时卖出一股，总收益为 $20$。

样例 #1

样例输入 #1

9
10 5 4 7 9 12 6 2 10

样例输出 #1

20

样例 #2

样例输入 #2

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

样例输出 #2

41

提示

In the first example, buy a share at $5$ , buy another at $4$ , sell one at $9$ and another at $12$ . Then buy at $2$ and sell at $10$ . The total profit is $-5-4+9+12-2+10=20$ .