题目背景

原题为 P9952 [USACO20OPEN] Social Distancing I B

题目描述

某实验室需要安装一批精密仪器，这些仪器需要保持适当间距以避免电磁干扰。实验室有一排共 $N$ $(2 \le N \le 10^5)$ 个安装位，部分位置已安装设备，部分位置空闲。定义间距 $D$ 为最近的两个已安装设备之间的距离。例如位置 $3$ 和 $8$ 是最近的安装位，则 $D=5$。

现在有两台新设备需要安装，请确定如何选择两个空闲位置进行安装，使得新的最小间距 $D$ 最大化。注意不能移动已有设备的位置。

输入格式

第一行包含整数 $N$。

第二行包含长度为 $N$ 的 $01$ 字符串，表示安装位状态 $0$ 表示空闲，$1$ 表示已占用。保证至少有两个 $0$。

输出格式

输出安装两台新设备后能获得的最大 $D$ 值。

输入输出样例

输入 #1

14
10001001000010

输出 #1

2

样例解释

最优安装方案为 10x010010x0010（x 表示新设备），此时最小间距 $D=2$。

数据范围

• 测试点 $1-6$：$N \le 20$
• 测试点 $7-8$：$N \le 100$
• 测试点 $9-11$：$N \le 5000$
• 测试点 $12-15$：无特殊限制