CF1700C.Helping the Nature

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$.

小狮子莱昂住在森林里。他最近注意到，他最喜欢的小径旁的一些树正在枯萎，而另一些树则水分过剩，因此他决定学习如何调控土壤湿度来拯救这些树木。

小径旁共有 $n$ 棵树，每棵树当前的湿度水平由数组 $a_1, a_2, \dots, a_n$ 表示。莱昂掌握了三种能力，可用于干燥或灌溉土壤：

• 选择一个位置 $i$，将第 $1, 2, \dots, i$ 棵树的湿度水平各减少 $1$；
• 选择一个位置 $i$，将第 $i, i + 1, \dots, n$ 棵树的湿度水平各减少 $1$；
• 将所有树的湿度水平各增加 $1$。

莱昂想知道：使每棵树的湿度恰好变为 $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$.

第一行包含一个整数 $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$。

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

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

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$.

在第一个测试用例中，只需对整个数组执行 $2$ 次加 $1$ 操作即可。

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

之后，对长度为 $1$ 的前缀执行 $6$ 次减操作，并对长度为 $1$ 的后缀执行 $3$ 次减操作。总共的操作次数为 $4 + 6 + 3 = 13$。可以证明，无法通过少于 $13$ 次操作得到目标数组，因此答案为 $13$。