← 返回题目列表

Codeforces · 1775/E

E. 人类方程式

中文机器翻译题面 查看原题

Petya 和他的朋友机器人 Petya++ 去了今天举行服装比赛的 BFDMONCON。

在穿过节日时,他们遇到了一个以 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$$$。

然后操作结束。另请注意,所有操作都是独立的,即。 e.当一项行动结束时,这些数字不再被称为北方或南方。

需要使用上述操作将序列的所有数字转为零。由于距离服装大赛只剩下很少的时间了,小伙伴们想知道,这次最少需要多少次操作。

朋友们无法解决这个问题,你能帮助他们吗?

$$$^\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$$$。

输出

对于每个测试用例,在一行中打印一个整数 - 将所有数字变成零所需的最少操作数。

示例

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

注意

在第一个测试用例中,操作顺序如下: $$$\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$$$。

在第四个测试用例中,只需选择整个序列作为子序列,然后将北边的数字减一,将南边的数字加一。因此,该序列将在一次操作中被清空。

在第五个测试用例中,您不需要执行任何操作,因为序列已经由零组成。