Problem Statement

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&Constraints

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.

Solving

在做此题之前，我们首先需要了解一下抽屉原理：

抽屉原理的定义 - 抽屉原理也被称为鸽巢原理。简单来说，如果有\(n + 1\)个物体要放进\(n\)个抽屉里，那么至少有一个抽屉里面会放有两个或者更多的物体。 - 例如，有3个苹果要放进2个抽屉，那么必然有一个抽屉里至少有2个苹果。

抽屉原理的一般形式 - 把\(m\)个物体放入\(n\)个抽屉中（\(m>n\)），则至少有一个抽屉里有\(k=\left\lceil\frac{m}{n}\right\rceil\)个物体（\(\left\lceil\frac{m}{n}\right\rceil\)表示向上取整）。 - 例如，把10个球放进3个抽屉，\(10\div3 = 3\cdots\cdots1\)，这里\(k=\left\lceil\frac{10}{3}\right\rceil = 4\)，即至少有一个抽屉里有4个球。

由于其向上取整的性质，我们可以得出若在有N只豚鼠的情况下，至少需要准备N/2 +1个笼子

所以我们只需在每次读取到b[i]==2时更新当前的笼子数量，然后在所有的更新结果中取他们的最大值就是答案：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int N = 0;
int t;    
void solve()
{
    int n;
    cin >> n;
    int b[n+1];
    int cnt = 0;
    int ans = 0;
    int house = 0;
    for(int i=1;i<=n;i++) cin >> b[i];
    for(int i=1;i<=n;i++)
    {
        if(b[i]==1) cnt++,house++;//未确定性别之前先一只一个笼子
        if(b[i]==2&&cnt)//确保在至少医生会来一次的情况下
        {
            house = cnt/2+1;//一旦确定后利用抽屉原理求最少笼子数
        }
        ans = max(ans,house);//每次更新取最大值
    }
    cout << ans << endl;
}
int main()
{
    ios::sync_with_stdio(false);cin.tie(nullptr);
    cin >> t;
    while(t--)
    {
        solve();
    }
    return 0;
}