Buy Low Sell High

题目描述

你可以完全预测某只股票接下来 N 天的价格。你希望利用这些信息获得尽可能多的收益，但每天至多只能交易一股股票：当天可以购买一股、卖出一股，或什么也不做。

开始时你没有持有任何股票；没有股票时不能卖出。第 N 天结束后，你也必须恰好不持有股票。

求最多能获得多少收益。

输入格式

第一行一个整数 N（2 <= N <= 3 * 10^5），表示天数。

第二行 N 个整数 p_1, p_2, ..., p_N（1 <= p_i <= 10^6），其中 p_i 表示第 i 天一股股票的价格。

输出格式

输出一个整数，表示最终能够获得的最大收益。

样例

样例 1

输入：

9
10 5 4 7 9 12 6 2 10

输出：

20

样例 2

输入：

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

输出：

41