CF1802B.Settlement of Guinea Pigs

Dasha loves guinea pigs very much. In this regard, she decided to settle as many guinea pigs at home as possible and developed a plan for the next $n$ days. Every day, she will either buy a new guinea pig or call a doctor to examine all her pets.

Unfortunately, the store where she was going to buy guinea pigs does not understand them. Therefore, it cannot determine their gender. Dasha can't do it either. The only one who can help is a doctor.

To keep guinea pigs, aviaries are needed. Dasha plans to buy them in the same store. Unfortunately, only one species is sold there — a double aviary. No more than two guinea pigs can live in it.

Since Dasha does not want to cause moral injury to her pets — she will not settle two guinea pigs of different genders in one aviary.

Help Dasha calculate how many aviaries in the worst case you need to buy so that you can be sure that at no moment of time do two guinea pigs of different genders live in the same aviary.

As part of this task, we believe that guinea pigs have only two genders — male and female.

达莎非常喜爱豚鼠。因此，她决定尽可能多地在家里饲养豚鼠，并为此制定了接下来 $n$ 天的计划。每天，她要么购买一只新的豚鼠，要么请医生来检查她所有的宠物。

不幸的是，她打算购买豚鼠的那家商店无法分辨豚鼠的性别，达莎自己也无法分辨。唯一能提供帮助的是医生。

为了饲养豚鼠，需要笼子。达莎计划在同一家商店购买笼子。但遗憾的是，该商店只出售一种笼子——双人笼。每个笼子最多可容纳两只豚鼠。

由于达莎不愿让她的宠物遭受心理伤害，她绝不会将不同性别的两只豚鼠安置在同一个笼子里。

请帮助达莎计算：在最坏情况下，她需要购买多少个笼子，才能确保在任意时刻，都不会有不同性别的两只豚鼠被安置在同一个笼子里。

本题中，我们假定豚鼠仅有两种性别——雄性和雌性。

The first line of input data contains one number $t$ ($1 \leqslant t \leqslant 10^5$) — the number of input data sets.

The first line of each input data set contains one number $n$ ($1 \leqslant n \leqslant 10^5$) — the number of days Dasha has a plan for.

The next line contains $n$ numbers $b_1, b_2, b_3, \ldots, b_n$ ($1 \leqslant b_i \leqslant 2$) — Dasha's plan. If $b_i = 1$, then on the $i$th day, Dasha will buy a new guinea pig. If $b_i = 2$, then on the $i$th day, a doctor will come to Dasha and help determine the sex of all guinea pigs that Dasha already has.

It is guaranteed that the sum of $n$ for all input data sets does not exceed $10^5$.

输入数据的第一行包含一个整数 $t$（$1 \leqslant t \leqslant 10^5$），表示输入数据组的数量。

每组输入数据的第一行包含一个整数 $n$（$1 \leqslant n \leqslant 10^5$），表示达莎已制定计划的天数。

下一行包含 $n$ 个整数 $b_1, b_2, b_3, \ldots, b_n$（$1 \leqslant b_i \leqslant 2$），表示达莎的计划：若 $b_i = 1$，则第 $i$ 天达莎将购买一只新的豚鼠；若 $b_i = 2$，则第 $i$ 天会有医生来访，帮助确定达莎当前拥有的所有豚鼠的性别。

保证所有输入数据组的 $n$ 值之和不超过 $10^5$。

For each set of input data, output one number — the minimum number of aviaries Dasha needs to buy so that no matter what the genders of the pigs turn out to be, we can settle them so that at no point in time do two guinea pigs of different genders live together.

对于每组输入数据，输出一个数字——达莎需要购买的最小笼子数量，使得无论豚鼠的性别如何，我们都能将它们安置好，从而在任何时刻都不会有不同性别的豚鼠共处一笼。

In the first set of input data, Dasha needs to put each guinea pig in a separate enclosure, since she does not know their gender.

In the second set of input data, Dasha will buy $0$ guinea pigs, which means she will need $0$ aviaries.

In the third set of input data, you even need $3$ aviaries to put each guinea pig in a separate aviary before the doctor arrives at the $4$th day. When she finds out their gender, at least two guinea pigs will be of the same gender and they can be placed in one aviary, and the third in another aviary. Thus, she will have one free aviary in which she can settle a new guinea pig. So answer is $3$.

In the fourth set of input data, we show that $4$ is the optimal answer.

To begin with, we note that the first four guinea pigs can be placed one at a time in an aviary. Then a doctor will come and determine their gender. Among these four guinea pigs there will be at least one pair of the same gender, because: either male guinea pigs are at least $2$, or they are not more than $1$, which means that the female is at least $3$. Now we can put this couple in one aviary, and the other two in separate ones. We will have one more empty aviary where we can put a new pig.

Now let's show that the answer is at least $4$. Let's say that among the first $4$ guinea pigs, $3$ are female and $1$ is male. We need at least $3$ aviaries to settle them. Then, when we buy a new guinea pig, we will need another aviary in which we will put it, since we do not know its gender.

在第一组输入数据中，达莎需要将每只豚鼠分别放入独立的围栏中，因为她不知道它们的性别。

在第二组输入数据中，达莎将购买 $0$ 只豚鼠，这意味着她只需要 $0$ 个鸟舍（aviary）。

在第三组输入数据中，甚至需要 $3$ 个鸟舍，才能在医生于第 $4$ 天到达之前，将每只豚鼠单独安置在一个鸟舍中。当她获知它们的性别后，至少有两只豚鼠性别相同，因此可将它们共同安置在一个鸟舍中，第三只则单独安置在另一个鸟舍中。于是，她将空出一个鸟舍，可用于安置一只新购入的豚鼠。因此答案为 $3$。

在第四组输入数据中，我们说明 $4$ 是最优解。

首先注意到：前四只豚鼠可依次各单独安置在一个鸟舍中；随后医生到来并确定它们的性别。在这四只豚鼠中，必存在至少一对同性别的豚鼠，理由如下：若雄性豚鼠数量不少于 $2$，则已满足；否则雄性豚鼠数量至多为 $1$，即雌性豚鼠数量至少为 $3$。此时，可将这一对同性别的豚鼠安置在一个鸟舍中，其余两只各安置在一个鸟舍中。这样便空出一个鸟舍，可用于安置一只新购入的豚鼠。

接下来我们证明答案至少为 $4$。假设前四只豚鼠中有 $3$ 只雌性、$1$ 只雄性，则至少需要 $3$ 个鸟舍来安置它们。随后，当再购入一只新豚鼠时，由于尚不知其性别，我们必须为其额外准备一个鸟舍。