The Human Equation

题意翻译

给定 $n$ 个数 $a_1...a_n$，随后你可以进行若干次操作，每次操作步骤如下： * 选出 $a$ 中一个子序列（可以不连续）。 * 把子序列中的奇数项减一，偶数项加一；或者奇数项加一，偶数项减一。 求把 $n$ 个数全部变成 $0$ 的最少操作次数。 $1\le n\le2\times10^5,-10^9\le a_i\le10^9$，多组数据。

题目描述

Petya and his friend, the robot Petya++, went to BFDMONCON, where the costume contest is taking place today. While walking through the festival, they came across a scientific stand named after Professor Oak and Golfball, where they were asked to solve an interesting problem. Given a sequence of numbers $ a_1, a_2, \dots, a_n $ you can perform several operations on this sequence. Each operation should look as follows. You choose some subsequence $ ^\dagger $ . Then you call all the numbers at odd positions in this subsequence northern, and all the numbers at even positions in this subsequence southern. In this case, only the position of the number in the subsequence is taken into account, not in the original sequence. For example, consider the sequence $ 1, 4, 2, 8, 5, 7, 3, 6, 9 $ and its subsequence (shown in bold) $ 1, \mathbf{4}, \mathbf{2}, 8, \mathbf{5}, 7, 3, \mathbf{6}, 9 $ . Then the numbers $ 4 $ and $ 5 $ are northern, and the numbers $ 2 $ and $ 6 $ are southern. After that, you can do one of the following: - add $ 1 $ to all northern numbers and subtract $ 1 $ from all south numbers; or - add $ 1 $ to all southern numbers and subtract $ 1 $ from all northern numbers. Thus, from the sequence $ 1, \mathbf{4}, \mathbf{2}, 8, \mathbf{5}, 7, 3, \mathbf{6}, 9 $ , if you choose the subsequence shown in bold, you can get either $ 1, \mathbf{5}, \mathbf{1}, 8, \mathbf{6}, 7, 3, \mathbf{5}, 9 $ or $ 1, \mathbf{3}, \mathbf{3}, 8, \mathbf{4}, 7, 3, \mathbf{7}, 9 $ . Then the operation ends. Note also that all operations are independent, i. e. the numbers are no longer called northern or southern when one operation ends. It is necessary to turn all the numbers of the sequence into zeros using the operations described above. Since there is very little time left before the costume contest, the friends want to know, what is the minimum number of operations required for this. The friends were unable to solve this problem, so can you help them? $ ^\dagger $ A sequence $ c $ is a subsequence of a sequence $ d $ if $ c $ can be obtained from $ d $ by the deletion of several (possibly, zero or all) elements.

输入输出格式

输入格式

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10^4 $ ). The description of the test cases follows. The first line of each test case contains an integer $ n $ ( $ 1 \le n \le 2\cdot 10^5 $ ) — the length of the sequence. The second line contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ -10^9 \le a_i \le 10^9 $ ) — the description of the sequence itself. It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2\cdot 10^5 $ .

输出格式

For each test case, print one integer in a single line — the minimum number of operations it takes to turn all the numbers into zeros.

输入输出样例

输入样例 #1

5
3
1 2 -3
5
1 0 0 -1 -1
6
2 -4 3 -5 4 1
5
1 -1 1 -1 1
7
0 0 0 0 0 0 0

输出样例 #1

3
2
6
1
0

说明

In the first test case, the sequence of operations is as follows: $ \mathbf{1}, 2, \mathbf{-3} \longrightarrow 0, \mathbf{2}, \mathbf{-2} \longrightarrow 0, \mathbf{1}, \mathbf{-1} \longrightarrow 0, 0, 0 $ . In the second test case, the sequence looks like this: $ \mathbf{1}, 0, 0, \mathbf{-1}, -1 \longrightarrow 0, 0, 0, 0, \mathbf{-1} \longrightarrow 0, 0, 0, 0, 0 $ . In the fourth test case, simply select the entire sequence as a subsequence, then subtract one from the northern numbers and add one to the southern numbers. Thus, the sequence will be nulled in one operation. In the fifth test case, you don't need to do any operations, since the sequence already consists of zeros.

**题意翻译**

给定 $n$ 个数 $a_1...a_n$，你可以进行多次操作，每次操作如下：

* 从 $a$ 中选择一个子序列（可以不连续）。
* 将子序列中的奇数项加一，偶数项减一；或者奇数项减一，偶数项加一。
* 目标是将所有数变成 $0$。
* 求：最少需要多少次操作。

输入输出数据格式：
- 输入：第一行包含测试用例数量 $t$，接下来每个测试用例有两行，第一行是数字数量 $n$，第二行是 $n$ 个数 $a_1, a_2, \ldots, a_n$。
- 输出：对于每个测试用例，输出一行，表示将序列中的所有数变成 $0$ 所需的最少操作次数。

**题目描述**

Petya 和他的朋友机器人 Petya++ 去了 BFDMONCON，那里正在进行服装比赛。在科学摊位上，他们被要求解决一个有趣的问题。

给你一个数列 $a_1, a_2, \ldots, a_n$，你可以在数列上进行多次操作。

每次操作如下。你选择一个子序列。然后你将子序列中奇数位置的数称为北方数，将偶数位置的数称为南方数。只考虑数在子序列中的位置，不考虑在原序列中的位置。

例如，考虑数列 $1, 4, 2, 8, 5, 7, 3, 6, 9$ 及其子序列（加粗部分）$1, \mathbf{4}, \mathbf{2}, 8, \mathbf{5}, 7, 3, \mathbf{6}, 9$。则数 $4$ 和 $5$ 是北方数，数 $2$ 和 $6$ 是南方数。

然后你可以做以下之一：
- 所有北方数加一，所有南方数减一；或者
- 所有南方数加一，所有北方数减一。

注意，所有操作是独立的，即一个操作结束后，数不再称为北方数或南方数。

目标是使用上述操作将数列的所有数变为零。由于服装比赛前时间不多，朋友们想知道，要达到这个目标，需要的最少操作次数是多少。

**输入输出格式**

输入：
- 第一行包含测试用例数量 $t$。
- 每个测试用例有两行，第一行是整数 $n$，第二行是 $n$ 个整数 $a_1, a_2, \ldots, a_n$。

输出：
- 对于每个测试用例，输出一行，表示将序列中的所有数变成 $0$ 所需的最少操作次数。

**输入输出样例**

输入样例 #1：
```
5
3
1 2 -3
5
1 0 0 -1 -1
6
2 -4 3 -5 4 1
5
1 -1 1 -1 1
7
0 0 0 0 0 0 0
```
输出样例 #1：
```
3
2
6
1
0
```**题意翻译** 给定 $n$ 个数 $a_1...a_n$，你可以进行多次操作，每次操作如下： * 从 $a$ 中选择一个子序列（可以不连续）。 * 将子序列中的奇数项加一，偶数项减一；或者奇数项减一，偶数项加一。 * 目标是将所有数变成 $0$。 * 求：最少需要多少次操作。 输入输出数据格式： - 输入：第一行包含测试用例数量 $t$，接下来每个测试用例有两行，第一行是数字数量 $n$，第二行是 $n$ 个数 $a_1, a_2, \ldots, a_n$。 - 输出：对于每个测试用例，输出一行，表示将序列中的所有数变成 $0$ 所需的最少操作次数。 **题目描述** Petya 和他的朋友机器人 Petya++ 去了 BFDMONCON，那里正在进行服装比赛。在科学摊位上，他们被要求解决一个有趣的问题。 给你一个数列 $a_1, a_2, \ldots, a_n$，你可以在数列上进行多次操作。 每次操作如下。你选择一个子序列。然后你将子序列中奇数位置的数称为北方数，将偶数位置的数称为南方数。只考虑数在子序列中的位置，不考虑在原序列中的位置。 例如，考虑数列 $1, 4, 2, 8, 5, 7, 3, 6, 9$ 及其子序列（加粗部分）$1, \mathbf{4}, \mathbf{2}, 8, \mathbf{5}, 7, 3, \mathbf{6}, 9$。则数 $4$ 和 $5$ 是北方数，数 $2$ 和 $6$ 是南方数。 然后你可以做以下之一： - 所有北方数加一，所有南方数减一；或者 - 所有南方数加一，所有北方数减一。 注意，所有操作是独立的，即一个操作结束后，数不再称为北方数或南方数。 目标是使用上述操作将数列的所有数变为零。由于服装比赛前时间不多，朋友们想知道，要达到这个目标，需要的最少操作次数是多少。 **输入输出格式** 输入： - 第一行包含测试用例数量 $t$。 - 每个测试用例有两行，第一行是整数 $n$，第二行是 $n$ 个整数 $a_1, a_2, \ldots, a_n$。 输出： - 对于每个测试用例，输出一行，表示将序列中的所有数变成 $0$ 所需的最少操作次数。 **输入输出样例** 输入样例 #1： ``` 5 3 1 2 -3 5 1 0 0 -1 -1 6 2 -4 3 -5 4 1 5 1 -1 1 -1 1 7 0 0 0 0 0 0 0 ``` 输出样例 #1： ``` 3 2 6 1 0 ```