← 返回题目列表

Codeforces · 1700/C

C. 帮助自然

中文机器翻译题面 查看原题

小莱昂住在森林里。他最近注意到他最喜欢的路径附近的一些树木正在枯萎,而其他树木则水分过多,因此他决定学习如何控制土壤湿度来拯救树木。

路径附近生长着 $$$n$$$ 棵树,每棵树当前的湿度水平由数组 $$$a_1, a_2, \dots, a_n$$$ 表示。莱昂学会了三种能力,可以帮助他干燥和浇水土壤。

- 选择一个位置 $$$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

4
3
-2 -2 -2
3
10 4 7
4
4 -4 4 -4
5
1 -2 3 -4 5

输出 #1

2
13
36
33

注意

在第一个测试用例中,将 $$$1$$$ 添加到整个数组 $$$2$$$ 次的操作就足够了。

在第二个测试用例中,您可以对长度为 $$$3$$$ 的前缀应用减少 $$$4$$$ 次的操作,并得到一个数组 $$$6, 0, 3$$$。

然后对长度$$$1$$$的前缀进行$$$6$$$次递减操作,对长度$$$1$$$的后缀进行$$$3$$$次递减操作。总共,操作数量为 $$$4 + 6 + 3 = 13$$$。可以看出,不可能执行更少的操作来获得所需的数组,因此答案是$$$13$$$。