Helping the Nature

题意翻译

给出一个长度为 $n$ 的序列 $a$，每次可以进行三种操作中的一种： - 选择 $i$，将 $a_1,a_2,\cdots,a_i$ 减 $1$。 - 选择 $i$，将 $a_i,a_{i+1},\cdots,a_n$ 减 $1$。 - 将所有 $a_i$ 加 $1$。 求最少需要多少次操作将所有 $a_i$ 变为 $0$。 $1\leq T\leq 2\times 10^4$，$1\leq n\leq 2\times 10^5$，$-10^9\leq a_i\leq 10^9$，$\sum n\leq 2\times 10^5$。

题目描述

Little Leon lives in the forest. He has recently noticed that some trees near his favourite path are withering, while the other ones are overhydrated so he decided to learn how to control the level of the soil moisture to save the trees. There are $ n $ trees growing near the path, the current levels of moisture of each tree are denoted by the array $ a_1, a_2, \dots, a_n $ . Leon has learned three abilities which will help him to dry and water the soil. - Choose a position $ i $ and decrease the level of moisture of the trees $ 1, 2, \dots, i $ by $ 1 $ . - Choose a position $ i $ and decrease the level of moisture of the trees $ i, i + 1, \dots, n $ by $ 1 $ . - Increase the level of moisture of all trees by $ 1 $ . Leon wants to know the minimum number of actions he needs to perform to make the moisture of each tree equal to $ 0 $ .

输入输出格式

输入格式

The first line contains a single integer $ t $ ( $ 1 \le t \le 2 \cdot 10^4 $ ) — the number of test cases. The description of $ t $ test cases follows. The first line of each test case contains a single integer $ n $ ( $ 1 \leq n \leq 200\,000 $ ). The second line of each test case contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ -10^9 \leq a_i \leq 10^9 $ ) — the initial levels of trees moisture. It is guaranteed that the sum of $ n $ over all test cases doesn't exceed $ 200\,000 $ .

输出格式

For each test case output a single integer — the minimum number of actions. It can be shown that the answer exists.

输入输出样例

输入样例 #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

说明

In the first test case it's enough to apply the operation of adding $ 1 $ to the whole array $ 2 $ times. In the second test case you can apply the operation of decreasing $ 4 $ times on the prefix of length $ 3 $ and get an array $ 6, 0, 3 $ . After that apply the operation of decreasing $ 6 $ times on the prefix of length $ 1 $ and $ 3 $ times on the suffix of length $ 1 $ . In total, the number of actions will be $ 4 + 6 + 3 = 13 $ . It can be shown that it's impossible to perform less actions to get the required array, so the answer is $ 13 $ .

**帮助自然**

**题意翻译：**
给出一个长度为 $ n $ 的序列 $ a $，可以进行以下三种操作：

- 选择 $ i $，将 $ a_1, a_2, \ldots, a_i $ 都减 $ 1 $。
- 选择 $ i $，将 $ a_i, a_{i+1}, \ldots, a_n $ 都减 $ 1 $。
- 将所有 $ a_i $ 都加 $ 1 $。

求最少需要多少次操作将所有 $ a_i $ 变为 $ 0 $。

数据限制：$ 1 \leq T \leq 2 \times 10^4 $，$ 1 \leq n \leq 2 \times 10^5 $，$ -10^9 \leq a_i \leq 10^9 $，所有测试案例中 $ n $ 的总和不超过 $ 2 \times 10^5 $。

**题目描述：**
小Leon生活在森林里。他最近注意到他最喜欢的路边的有些树正在枯萎，而有些树则水分过多，所以他决定学习如何控制土壤的水分水平来拯救这些树。

路边的 $ n $ 棵树，每棵树的水分水平由数组 $ a_1, a_2, \ldots, a_n $ 表示。Leon学会了三种技能来干燥和浇灌土壤：

- 选择一个位置 $ i $，将 $ 1, 2, \ldots, i $ 号树的水分水平减 $ 1 $。
- 选择一个位置 $ i $，将 $ i, i+1, \ldots, n $ 号树的水分水平减 $ 1 $。
- 将所有树的水分水平加 $ 1 $。

Leon想知道他需要执行的最少操作次数，使每棵树的水分水平等于 $ 0 $。

**输入输出格式：**

**输入格式：**
第一行包含一个整数 $ t $（$ 1 \le t \le 2 \times 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 $ 的操作就足够了。

在第二个测试案例中，可以对长度为 $ 3 $ 的前缀进行 $ 4 $ 次减操作，得到数组 $ 6, 0, 3 $。

然后对长度为 $ 1 $ 的前缀进行 $ 6 $ 次减操作，对长度为 $ 1 $ 的后缀进行 $ 3 $ 次减操作。总共的操作次数将是 $ 4 + 6 + 3 = 13 $。可以证明不可能通过更少的操作得到所需的数组，所以答案是 $ 13 $。**帮助自然** **题意翻译：** 给出一个长度为 $ n $ 的序列 $ a $，可以进行以下三种操作： - 选择 $ i $，将 $ a_1, a_2, \ldots, a_i $ 都减 $ 1 $。 - 选择 $ i $，将 $ a_i, a_{i+1}, \ldots, a_n $ 都减 $ 1 $。 - 将所有 $ a_i $ 都加 $ 1 $。 求最少需要多少次操作将所有 $ a_i $ 变为 $ 0 $。 数据限制：$ 1 \leq T \leq 2 \times 10^4 $，$ 1 \leq n \leq 2 \times 10^5 $，$ -10^9 \leq a_i \leq 10^9 $，所有测试案例中 $ n $ 的总和不超过 $ 2 \times 10^5 $。 **题目描述：** 小Leon生活在森林里。他最近注意到他最喜欢的路边的有些树正在枯萎，而有些树则水分过多，所以他决定学习如何控制土壤的水分水平来拯救这些树。 路边的 $ n $ 棵树，每棵树的水分水平由数组 $ a_1, a_2, \ldots, a_n $ 表示。Leon学会了三种技能来干燥和浇灌土壤： - 选择一个位置 $ i $，将 $ 1, 2, \ldots, i $ 号树的水分水平减 $ 1 $。 - 选择一个位置 $ i $，将 $ i, i+1, \ldots, n $ 号树的水分水平减 $ 1 $。 - 将所有树的水分水平加 $ 1 $。 Leon想知道他需要执行的最少操作次数，使每棵树的水分水平等于 $ 0 $。 **输入输出格式：** **输入格式：** 第一行包含一个整数 $ t $（$ 1 \le t \le 2 \times 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 $ 的操作就足够了。 在第二个测试案例中，可以对长度为 $ 3 $ 的前缀进行 $ 4 $ 次减操作，得到数组 $ 6, 0, 3 $。 然后对长度为 $ 1 $ 的前缀进行 $ 6 $ 次减操作，对长度为 $ 1 $ 的后缀进行 $ 3 $ 次减操作。总共的操作次数将是 $ 4 + 6 + 3 = 13 $。可以证明不可能通过更少的操作得到所需的数组，所以答案是 $ 13 $。