Description：

有 $n$ 个位置，每个位置可能有人也可能没有，在任意时刻如果有一个人前面没有人，他就会向前走一步，问多长时间所有人都走到了最终位置。

$1\leqslant n\leqslant 10^5$

Solution：

设 $g[i]$ 表示位置 $i$ 上的人走到开始的最短时间，那么如果它刚开始就已经归位了，那么 $g[i]=0$ ，否则他要么一直走到归位，要么被他前一个人卡住，所以 $g[i]=\max(i-cnt,g[last])$ 。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

#define R register

inline int rd()

{

	R char c = getchar();

	while(c != '0' && c != '1')c = getchar();

	return c - '0';

}

int n;

#define MAXN 100010

int a[MAXN];

int s[MAXN];

void work()

{

	scanf("%d",&n);

	for(int i = 1;i <= n;++i)a[i] = rd();

	int last = 0;

	int cnt = 0;

	int i;

	for(i = 1;i <= n;++i)

	{

		if(a[i] == 0)

		{

			last = i - 1;

			break;

		}

		++cnt;//cout << s[i] << " ";

	}

	memset(s,0,sizeof(s));

	for(;i <= n;++i)

	{

		if(a[i])

		{

			s[i] = max(s[last] + 1,i - cnt - 1);

			last = i;

			++cnt;

		}//cout << s[i] << " ";

	}//cout << endl;

	int ans = 0;

	for(int i = 1;i <= n;++i)

	{

		ans = max(ans,s[i]);

	}

	cout << ans << endl;

	return;

}

int main()

{

	freopen("ambush.in","r",stdin);

	freopen("ambush.out","w",stdout);

	int testcases;

	scanf("%d",&testcases);

	while(testcases--)work();

	fclose(stdin);

	fclose(stdout);

	return 0;

}