CF1700C Helping the Nature

小 Leon 住在森林里。他最近注意到他最喜欢的小路旁的一些树正在枯萎，而其他一些树则水分过多，于是他决定学习如何控制土壤的湿度来拯救这些树。 小路旁有 $n$ 棵树，每棵树当前的土壤湿度分别用数组 $a_1, a_2, \dots, a_n$ 表示。Leon 学会了三种技能，可以帮助他给土壤加水或排水： - 选择一个位置 $i$，将第 $1, 2, \dots, i$ 棵树的湿度各减少 $1$。 - 选择一个位置 $i$，将第 $i, i+1, \dots, n$ 棵树的湿度各减少 $1$。 - 将所有树的湿度都增加 $1$。 Leon 想知道，最少需要多少次操作，才能使每棵树的湿度都变为 $0$。

第一行包含一个整数 $t$（$1 \le t \le 2 \cdot 10^4$）——表示测试用例的数量。接下来是 $t$ 组测试用例。 每组测试用例的第一行包含一个整数 $n$（$1 \leq n \leq 200\,000$）。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$-10^9 \leq a_i \leq 10^9$），表示每棵树初始的湿度。 保证所有测试用例中 $n$ 的总和不超过 $200\,000$。

对于每组测试用例，输出一个整数，表示最少需要的操作次数。可以证明答案一定存在。

在第一个测试用例中，只需对整个数组执行两次“所有树湿度加 $1$”的操作即可。 在第二个测试用例中，可以对前缀长度为 $3$ 的部分执行 $4$ 次减少操作，此时数组变为 $6, 0, 3$。 之后对前缀长度为 $1$ 的部分执行 $6$ 次减少操作，对后缀长度为 $1$ 的部分执行 $3$ 次减少操作。总操作次数为 $4 + 6 + 3 = 13$。可以证明无法用更少的操作使所有树的湿度变为 $0$，因此答案为 $13$。 由 ChatGPT 4.1 翻译