题目描述

Prgl 是股票大师，可以完美预测某支股票未来 $N$ 天的价格。Prgl 想借此获利，但他只想每天交易一股股票。也就是说，每天他要么买入一股，要么卖出一股（如果手中有股票），要么什么都不做。最初 Prgl 没有股票。在 $N$ 天结束时，Prgl 希望自己的手中没有股票，但拥有尽可能多的钱。

输入格式

输入第一行一个整数 $N(2\le N\le 3\cdot 10^5)$ 表示天数。

接下来一行 $N$ 个整数 $p_1,p_2,\dots,p_N(1\le p_i\le 10^6)$。表示每一天股票的价格。

输出格式

输出 Prgl 在第 $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

Note

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.