描述

您可以完美地预测某只股票在接下来 N 天的价格。您希望利用这一知识获利，但每天最多只想交易一股股票。也就是说，每天您要么购买一股，要么卖出一股，要么选择不做任何操作。最开始您没有持有任何股票，且在没有持股的情况下不能进行卖出操作。在 N 天结束时，您希望再次持有零股，但希望尽可能拥有更多的钱。

输入格式

输入以一个整数 N 开始（2 ≤ N ≤ 3·105），表示天数。

接下来是一行恰好包含 N 个整数 p1, p2, ..., pN（1 ≤ pi ≤ 106）。第 i 天的股票价格为 pi。

输出格式

输出您在 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。