达莎非常喜欢豚鼠。对此,她决定在家里安顿尽可能多的豚鼠,并为接下来的几天制定了计划。每天,她要么买一只新的豚鼠,要么请医生检查她所有的宠物。
不幸的是,她要买豚鼠的商店不懂它们。因此,它无法确定他们的性别。达莎也做不到。唯一能提供帮助的是医生。
为了饲养豚鼠,需要鸟舍。达莎打算在同一家商店购买它们。不幸的是,那里只出售一种鸟——双鸟舍。里面最多只能住两只豚鼠。
由于达莎不想对她的宠物造成精神伤害——她不会在一个鸟舍里安置两只不同性别的豚鼠。
帮助达莎计算一下在最坏的情况下你需要购买多少个鸟舍,这样你就可以确定在任何时候两只不同性别的豚鼠都不会生活在同一个鸟舍里。
作为这项任务的一部分,我们认为豚鼠只有两种性别——雄性和雌性。
输入
输入数据的第一行包含一个数字 $$$t$$$ ($$$1 \leqslant t \leqslant 10^5$$$) — 输入数据集的数量。
每个输入数据集的第一行包含一个数字 $$$n$$$ ($$$1 \leqslant n \leqslant 10^5$$$) — Dasha 计划的天数。
下一行包含 $$$n$$$ 数字 $$$b_1, b_2, b_3, \ldots, b_n$$$ ($$$1 \leqslant b_i \leqslant 2$$$) — Dasha 的计划。如果 $$$b_i = 1$$$,那么在第 $$$i$$$ 天,Dasha 将购买一只新豚鼠。如果$$$b_i = 2$$$,那么在$$$i$$$第$$$i$$$天,医生会来到Dasha身边,帮助确定Dasha已有的所有豚鼠的性别。
保证所有输入数据集的$$$n$$$总和不超过$$$10^5$$$。
输出
对于每组输入数据,输出一个数字——Dasha需要购买的最小鸟舍数量,这样无论猪的性别如何,我们都可以解决它们,这样在任何时候都不会出现两只不同性别的豚鼠生活在一起。
示例
输入 #1
6 3 1 1 1 3 2 2 2 5 1 1 1 2 1 10 1 2 1 2 1 2 1 2 1 2 20 1 2 1 1 1 1 1 2 1 2 1 2 2 1 1 1 1 1 1 1 20 2 1 1 2 1 1 2 1 2 2 1 1 1 2 2 1 1 1 1 2
输出 #1
3 0 3 4 12 9
注意
在第一组输入数据中,Dasha 需要将每只豚鼠放在单独的围栏中,因为她不知道它们的性别。
在第二组输入数据中,Dasha 将购买 $$$0$$$ 豚鼠,这意味着她将需要 $$$0$$$ 鸟舍。
在第三组输入数据中,您甚至需要 $$$3$$$ 鸟舍在医生到达第 $$$4$$$ 天之前将每只豚鼠放入单独的鸟舍中。当她确定它们的性别时,至少有两只豚鼠是相同性别的,可以将它们放入一个鸟舍,将第三只放入另一个鸟舍。因此,她将拥有一个免费的鸟舍,可以在其中安置一只新的豚鼠。所以答案是$$$3$$$。
在第四组输入数据中,我们表明 $$$4$$$ 是最佳答案。
首先,我们注意到前四只豚鼠可以一次放入鸟舍中。然后医生会来确定他们的性别。这四只豚鼠中至少会有一对相同性别,因为:要么雄性豚鼠至少$$$2$$$,要么不超过$$$1$$$,这意味着雌性至少$$$3$$$。现在我们可以将这对夫妇放在一个鸟舍中,将另外两个放在不同的鸟舍中。我们将再有一个空鸟舍,可以在那里放一头新猪。
现在让我们证明答案至少是 $$$4$$$。假设在第一批 $$$4$$$ 豚鼠中,$$$3$$$ 是雌性,$$$1$$$ 是雄性。我们至少需要 $$$3$$$ 鸟舍来安置它们。然后,当我们购买新的豚鼠时,我们将需要另一个鸟舍来放置它,因为我们不知道它的性别。