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