← 返回题目列表

Codeforces · 1923/A

A. 移动筹码

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

有一个功能区,分为 $$$n$$$ 个单元格,从左到右编号为 $$$1$$$ 到 $$$n$$$。每个单元要么包含一个芯片,要么是免费的。

您可以执行以下操作任意次数(可能为零):选择一个筹码并将其移动到左侧最近的空闲单元。您可以选择任何您想要的芯片,只要其左侧至少有一个空闲单元即可。当您移动芯片时,操作前所在的单元格就会空闲。

您的目标是移动芯片,使它们形成一个块,并且它们之间没有任何空闲单元。您必须执行的最少操作次数是多少?

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。

每个测试用例由两行组成:

- 第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 50$$$) — 单元格数量;
- 第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 1$$$); $$$a_i = 0$$$ 表示第 $$$i$$$ 个单元格空闲; $$$a_i = 1$$$ 表示第 $$$i$$$ 个单元包含一个芯片。

对输入的附加约束:在每个测试用例中,至少一个单元包含芯片。

输出

对于每个测试用例,打印一个整数 - 您必须执行的最小操作数,以便所有芯片形成一个块,并且它们之间没有任何空闲单元。

示例

输入 #1

5
8
0 1 1 1 0 1 1 0
6
0 1 0 0 0 0
6
1 1 1 1 1 1
5
1 0 1 0 1
9
0 1 1 0 0 0 1 1 0

输出 #1

1
0
0
2
3

注意

在第一个示例中,您可以对第 $$$7$$$ 单元格中的芯片执行操作。左边最近的空闲单元格是第 $$$5$$$ 个单元格,因此它会移动到那里。之后,所有芯片形成一个块。

在第二个示例中,所有芯片都已位于单个块中。第三个例子也一样。