← 返回题目列表

Codeforces · 1649/A

A. 游戏

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

您正在玩一款非常流行的电脑游戏。下一个级别由 $$$n$$$ 连续位置组成,编号从 $$$1$$$ 到 $$$n$$$,每个位置包含土地或水域。众所周知,第一个和最后一个位置包含土地,要完成关卡,您必须从第一个位置移动到最后一个位置。另外,如果你进入有水的地方,你就会死,所以你只能在有陆地的地方之间移动。

你可以免费在相邻位置之间跳跃,并且从任何有土地 $$$i$$$ 的位置跳跃到任何有土地 $$$i + x$$$ 的位置不超过一次,花费 $$$x$$$ 硬币 ($$$x \geq 0$$$)。

你的任务是花费尽可能少的硬币从第一个位置移动到最后一个位置。

请注意,这始终是可能的,因为第一个和最后一个位置都是陆地位置。

输入

输入数据中有多个测试用例。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 100$$$) — 测试用例的数量。接下来是测试用例描述。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \leq n \leq 100$$$) — 位置数。

测试用例的第二行包含整数序列 $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i \leq 1$$$),其中 $$$a_i = 1$$$ 表示第 $$$i$$$ 位置是有土地的位置,$$$a_i = 0$$$ 表示第$$$i$$$位置是有水的位置。保证 $$$a_1 = 1$$$ 且 $$$a_n = 1$$$。

输出

对于每个测试用例,打印一个整数 - 问题的答案。

示例

输入 #1

3
2
1 1
5
1 0 1 0 1
4
1 0 1 1

输出 #1

0
4
2

注意

在第一个测试用例中,从第一个位置自由跳转到第二个位置(也是最后一个位置)就足够了,所以答案是 $$$0$$$。

在第二个测试用例中,从第一个位置移动到最后一个位置的唯一方法是在它们之间跳转,这将花费 $$$4$$$ 硬币。

在第三个测试用例中,你可以从第一个位置跳到第三个位置,花费$$$2$$$硬币,然后免费跳到第四个位置,所以答案是$$$2$$$。可以证明这是最优的方式。