#P1700C. Helping the Nature

    ID: 7729 Type: RemoteJudge 2000ms 256MiB Tried: 0 Accepted: 0 Difficulty: (None) Uploaded By: Tags>constructive algorithmsdata structuresgreedy*1700

Helping the Nature

No submission language available for this problem.

Description

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 nn trees growing near the path, the current levels of moisture of each tree are denoted by the array a1,a2,,ana_1, a_2, \dots, a_n. Leon has learned three abilities which will help him to dry and water the soil.

  • Choose a position ii and decrease the level of moisture of the trees 1,2,,i1, 2, \dots, i by 11.
  • Choose a position ii and decrease the level of moisture of the trees i,i+1,,ni, i + 1, \dots, n by 11.
  • Increase the level of moisture of all trees by 11.

Leon wants to know the minimum number of actions he needs to perform to make the moisture of each tree equal to 00.

The first line contains a single integer tt (1t21041 \le t \le 2 \cdot 10^4)  — the number of test cases. The description of tt test cases follows.

The first line of each test case contains a single integer nn (1n2000001 \leq n \leq 200\,000).

The second line of each test case contains nn integers a1,a2,,ana_1, a_2, \ldots, a_n (109ai109-10^9 \leq a_i \leq 10^9) — the initial levels of trees moisture.

It is guaranteed that the sum of nn over all test cases doesn't exceed 200000200\,000.

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

Input

The first line contains a single integer tt (1t21041 \le t \le 2 \cdot 10^4)  — the number of test cases. The description of tt test cases follows.

The first line of each test case contains a single integer nn (1n2000001 \leq n \leq 200\,000).

The second line of each test case contains nn integers a1,a2,,ana_1, a_2, \ldots, a_n (109ai109-10^9 \leq a_i \leq 10^9) — the initial levels of trees moisture.

It is guaranteed that the sum of nn over all test cases doesn't exceed 200000200\,000.

Output

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

Samples

Sample Input 1

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

Sample Output 1

2
13
36
33

Note

In the first test case it's enough to apply the operation of adding 11 to the whole array 22 times.

In the second test case you can apply the operation of decreasing 44 times on the prefix of length 33 and get an array 6,0,36, 0, 3.

After that apply the operation of decreasing 66 times on the prefix of length 11 and 33 times on the suffix of length 11. In total, the number of actions will be 4+6+3=134 + 6 + 3 = 13. It can be shown that it's impossible to perform less actions to get the required array, so the answer is 1313.