挑战塔 - 代码源竞赛平台

题目描述

蜗蜗和朋友在游戏里挑战一座塔，塔内有按顺序编号的 $n$ 个 Boss。第 $i$ 个 Boss 的类型为 $a_i$：$0$ 表示简单，$1$ 表示困难。

两人轮流行动，朋友先手。每次行动者必须击败接下来的 $1$ 个或 $2$ 个 Boss，不能跳过回合，也不能越过尚未击败的 Boss。蜗蜗可以直接击败任意 Boss；朋友遇到困难 Boss 时，每击败一个就要消耗 $1$ 个跳过点数，击败简单 Boss 不消耗点数。

对于每组数据，求两人击败所有 Boss 时，朋友最少需要消耗多少跳过点数。

输入格式

第一行包含一个整数 $t$，表示测试用例数。

对于每组测试用例，第一行包含一个整数 $n$，第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

输出格式

对于每组测试用例，输出一行一个整数，表示朋友最少消耗的跳过点数。

样例

2
3
1 1 0
4
0 1 1 0

1
0

2
1
0
2
1 1

0
1

样例解释

样例 1 的第一组数据中，朋友先击败第 $1$ 个 Boss，蜗蜗再击败第 $2$、第 $3$ 个，朋友只需 $1$ 个跳过点数。第二组数据中，朋友先击败第 $1$ 个，蜗蜗击败第 $2$、第 $3$ 个，朋友击败第 $4$ 个，不消耗跳过点数。

样例 2 的两组数据，最少消耗分别为 $0$ 和 $1$。

数据范围

对于 100% 的数据，保证 $1\le t\le 2\times 10^4$，$1\le n\le 2\times 10^5$，$a_i\in\{0,1\}$；同一输入中所有测试用例的 $n$ 之和不超过 $2\times 10^5$。