You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

小 Z 最近沉迷各类下棋游戏，小 Y 见状立马给小 Z 出了一个策略下棋游戏。这个游戏很怪，棋盘只有 $1$ 行 $n$ 列，可以看作是长长的 $n$ 个格子排成的一排。

这些格子里面有些已经落了棋子，有些还没有落的（格子是空的），我们落子需要在空的格子里落子。游戏的目标是要使得最终相邻的两个有棋子的格子之间距离越大越好，假设这个距离为 $d$。

例如，我们用 $0$ 表示空格子，$1$ 表示有棋子的格子，有 $14$ 个格子的棋盘状态如下：

• $10001001000010$

• 那么，相邻有棋子的格子距离分别为 $4,3,5$，其中最近的距离为 $3$，也就是 $d=3$。

现在小 Z 需要再在棋盘中落下两个棋子，他只能把棋子下在空格子里，并且要保证所有相邻有棋子的格子之间的距离 $d$ 越大越好，问 $d$ 最大为多少。小 Z 不能移动原来的任何棋子。

例如，在上述状态的棋盘中，小 Z 可以在 $3,10$ 格子中落下棋子，下棋状态为 10x010010x0010,其中 x 表示新落下的棋子，这样下棋后 $d = 2$。

输入格式

第一行一个正整数 $n$ 表示棋盘格子数。

第二行一个长度为 $n$ 的 $01$ 字符串表示棋盘的初始状态。

输出格式

输出小 Z 落下两个棋子后，棋盘可以达到的最大的 $d$，也就是相邻棋子之间最近距离的最大值。

样例 #1

样例输入 #1

14
10001001000010

样例输出 #1

2

提示

测试点 $1-5$ 满足 $N≤10$。

测试点 $6-7$ 满足 $N≤100$。

测试点 $8-10$ 满足 $N≤5000$。

测试点 $11-14$ 满足 $2\le n \le 2 * 10^5$。