310236: CF1802B. Settlement of Guinea Pigs

B. Settlement of Guinea Pigstime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

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.

Input

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$.

Output

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.

ExampleInput

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

Output

3
0
3
4
12
9

Note

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.

题目大意：
Dasha非常喜欢豚鼠，她决定尽可能多地在家养豚鼠，并为此制定了未来n天的计划。每天，她要么买一只新的豚鼠，要么请医生来检查她所有的宠物。

不幸的是，她打算购买豚鼠的商店无法分辨它们的性别。Dasha也无法做到这一点。唯一能提供帮助的是医生。

为了养豚鼠，需要笼子。Dasha计划在同一个商店购买。不幸的是，那里只卖一种——双人笼子。每个笼子最多只能住两只豚鼠。

由于Dasha不想对她的宠物造成道德伤害——她不会让两只不同性别的豚鼠住在同一个笼子里。

帮助Dasha计算在最坏的情况下，她需要购买多少个笼子，以确保在任何时刻都不让两只不同性别的豚鼠住在同一个笼子里。

输入输出数据格式：
输入数据的第一行包含一个数字t（1≤t≤10^5）——输入数据集的数量。

每个输入数据集的第一行包含一个数字n（1≤n≤10^5）——Dasha的计划天数。

下一行包含n个数字b1, b2, b3, …, bn（1≤bi≤2）——Dasha的计划。如果bi=1，则表示第i天Dasha将购买一只新的豚鼠。如果bi=2，则表示在第i天医生会来帮助Dasha确定她已有的所有豚鼠的性别。

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

对于每个输入数据集，输出一个数字——Dasha需要购买的最少笼子数量，以确保无论豚鼠的性别如何，我们都可以将它们安置好，使得在任何时刻都没有两只不同性别的豚鼠住在同一个笼子里。题目大意： Dasha非常喜欢豚鼠，她决定尽可能多地在家养豚鼠，并为此制定了未来n天的计划。每天，她要么买一只新的豚鼠，要么请医生来检查她所有的宠物。 不幸的是，她打算购买豚鼠的商店无法分辨它们的性别。Dasha也无法做到这一点。唯一能提供帮助的是医生。 为了养豚鼠，需要笼子。Dasha计划在同一个商店购买。不幸的是，那里只卖一种——双人笼子。每个笼子最多只能住两只豚鼠。 由于Dasha不想对她的宠物造成道德伤害——她不会让两只不同性别的豚鼠住在同一个笼子里。 帮助Dasha计算在最坏的情况下，她需要购买多少个笼子，以确保在任何时刻都不让两只不同性别的豚鼠住在同一个笼子里。 输入输出数据格式： 输入数据的第一行包含一个数字t（1≤t≤10^5）——输入数据集的数量。 每个输入数据集的第一行包含一个数字n（1≤n≤10^5）——Dasha的计划天数。 下一行包含n个数字b1, b2, b3, …, bn（1≤bi≤2）——Dasha的计划。如果bi=1，则表示第i天Dasha将购买一只新的豚鼠。如果bi=2，则表示在第i天医生会来帮助Dasha确定她已有的所有豚鼠的性别。 保证所有输入数据集的n之和不超过10^5。 对于每个输入数据集，输出一个数字——Dasha需要购买的最少笼子数量，以确保无论豚鼠的性别如何，我们都可以将它们安置好，使得在任何时刻都没有两只不同性别的豚鼠住在同一个笼子里。