测试数据来自 system/2901

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

时间限制：1秒　　内存限制：256M

---

【题目描述】

　　C城有一座监狱，监狱中有 \(n(n≤200000)\) 个牢房，这些牢房一字排开，第i个牢房紧挨着第 \(i+1\) 个牢房（最后一个除外），第 \(i\) 个牢房紧挨着第 \(i-1\) 个牢房（第一个除外）。有些牢房中关押有罪犯，有些则是空着的。

　　罪犯总是很暴躁的，若相邻两个罪犯的牢房过于靠近，他们之间时常会搞出一些事端，给看守们增加无尽的烦恼。因此监狱长总是想法设法第让距离最近的罪犯之间的距离d尽量大。例如，如果牢房 3 和 8 是最近的有罪犯的牢房，那么 \(d=5\)。

　　最近两个罪犯新来到监狱，监狱长需要决定将他们分配到哪两个之前空着的牢房。请求出他如何安置这两个新来的罪犯，使得 \(d\) 仍然尽可能大。监狱长不能移动任何已有的罪犯；他只想要给新来的罪犯分配牢房。

【输入格式】

　　输入的第一行包含 \(n\)。下一行包含一个长为 \(n\) 的字符串，由 0 和1 组成，描述监狱里的牢房。0 表示空着的牢房，1 表示有罪犯的牢房。字符串中包含至少两个 0，所以有至少有足够的空间安置两个新来的罪犯。

【输出格式】

　　输出监狱长以最优方案在加入两个新来的罪犯后可以达到的最大 \(d\) 值（最近的罪犯之间的距离）。

【输入输出样例】

　Input

23
00100000010000100010000

　Output

3

【样例解释】

　　监狱长可以以这样的方式加入罪犯，使得牢房分配变为 00100 z 000100001000100 z 0 ，其中 z 表示新来的罪犯。此时 \(d=3\)。不可能在加入罪犯之后取到更大的 \(d\) 值。

【测试点性质】

　　测试点 \(2−6\) 满足 \(n≤10\)。
　　测试点 \(7−8\) 满足 \(n≤100\)。
　　测试点 \(9−11\) 满足 \(n≤5000\)。
　　测试点 \(12−15\) 没有额外限制。

【来源】

　　Mr.he