CF1775E The Human Equation

Petya 和他的朋友机器人 Petya++ 一起去了 BFDMONCON，今天那里正在举办服装比赛。 在逛节日时，他们遇到了以 Professor Oak 和 Golfball 命名的科学展台，在那里他们被要求解决一个有趣的问题。 给定一个数列 $a_1, a_2, \dots, a_n$，你可以对该数列进行若干次操作。 每次操作如下：你选择一个子序列 $^\dagger$。然后，将该子序列中所有奇数位置的数字称为“北方数”，所有偶数位置的数字称为“南方数”。这里指的是在子序列中的位置，而不是原序列中的位置。 例如，考虑序列 $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$ 是南方数。 接下来，你可以进行以下两种操作之一： - 对所有北方数加 $1$，对所有南方数减 $1$；或者 - 对所有南方数加 $1$，对所有北方数减 $1$。 因此，对于序列 $1, \mathbf{4}, \mathbf{2}, 8, \mathbf{5}, 7, 3, \mathbf{6}, 9$，如果选择上述粗体子序列，你可以得到 $1, \mathbf{5}, \mathbf{1}, 8, \mathbf{6}, 7, 3, \mathbf{5}, 9$ 或 $1, \mathbf{3}, \mathbf{3}, 8, \mathbf{4}, 7, 3, \mathbf{7}, 9$。 然后本次操作结束。注意所有操作彼此独立，即每次操作结束后，数字不再被称为北方数或南方数。 你需要通过上述操作将序列中的所有数字都变为零。由于离服装比赛开始的时间不多了，朋友们想知道，最少需要多少次操作才能做到这一点。 朋友们无法解决这个问题，你能帮帮他们吗？ $^\dagger$ 序列 $c$ 是序列 $d$ 的子序列，如果 $c$ 可以通过从 $d$ 中删除若干（可能为零或全部）元素得到。

每个测试用例包含多组数据。第一行包含测试用例数 $t$（$1 \le t \le 10^4$）。接下来是每组测试用例的描述。 每组测试用例的第一行包含一个整数 $n$（$1 \le n \le 2\cdot 10^5$），表示序列的长度。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$-10^9 \le a_i \le 10^9$），表示该序列。 保证所有测试用例中 $n$ 的总和不超过 $2\cdot 10^5$。

对于每组测试用例，输出一个整数，表示将所有数字变为零所需的最少操作次数。

在第一个测试用例中，操作序列如下：$\mathbf{1}, 2, \mathbf{-3} \longrightarrow 0, \mathbf{2}, \mathbf{-2} \longrightarrow 0, \mathbf{1}, \mathbf{-1} \longrightarrow 0, 0, 0$。 在第二个测试用例中，操作序列如下：$\mathbf{1}, 0, 0, \mathbf{-1}, -1 \longrightarrow 0, 0, 0, 0, \mathbf{-1} \longrightarrow 0, 0, 0, 0, 0$。 在第四个测试用例中，只需选择整个序列作为子序列，然后对北方数减一、南方数加一即可。因此，只需一次操作即可将序列全部变为零。 在第五个测试用例中，不需要进行任何操作，因为序列已经全为零。 由 ChatGPT 4.1 翻译