星际贸易

题目描述

在广阔的银河系中，你驾驶着一艘货船穿梭于各个行星之间。你发现一种名为“星石”的稀有能源矿产在不同的日子里价格会有所波动。

已知未来 $n$ 天内，每天星石的价格为 $a_i$。由于货船容量有限，你手中最多只能同时持有一颗星石。你可以在任何一天买入星石，也可以在任何一天卖出你手中的星石。交易次数不限，但你必须在买入下一颗星石之前，先卖掉当前持有的星石。

你的目标是利用价格波动，计算出在 $n$ 天结束时，你能获得的最大利润是多少？

输入格式

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

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，表示每天星石的价格。

输出格式

输出一个整数，表示能获得的最大利润。

输入输出样例 #1

输入 #1

6
7 1 5 3 6 4

输出 #1

7

输入输出样例 #2

输入 #2

5
1 2 3 4 5

输出 #2

4

数据范围

对于 $60\%$ 的数据，$1 \le n \le 1000$。

对于 $100\%$ 的数据，$1 \le n \le 10^5$，$0 \le a_i \le 10^9$。