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

题目描述

一年一度的《跳石头》大赛又要开始了！ 这项比赛将在一条笔直的河道中进行，河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终点。 包含起点和终点在内，一共有 N 块岩石，其中 1 号石头是起点，N 号石头是终点，并且任意相邻两个编号的石头之间的距离都是 1 。 在比赛过程中，选手们将从起点出发，每一步跳向相邻的岩石，直至到达终点即可获胜。 为了提高比赛难度，组委会计划标记一些岩石，选手们在比赛过程中不允许跳到被标记的岩石上。 现在谢老师为了准备《跳石头》大赛，提前开始锻炼自己的跳跃能力。 假设谢老师的跳跃能力为 x，那么他每次可以最多跳跃 x 的距离，即可以从 i 号岩石一步跳到 [i+1, i+x] 中的任意一块岩石。 现在谢老师想知道，他至少要把跳跃能力锻炼到多少，才能保证获胜？

输入格式

输入第一行包含一个正整数 n，表示岩石数量。 输入第二行包含 n 个正整数 a_i 表示编号为 i 的岩石是否被标记，若 a_i=0 则这块石头被标记。

输出格式

输出一个整数，表示谢老师至少需要的跳跃能力。

数据范围

对于 20% 的数据，满足 1 <= n <= 50，除起点终点外所有 a_i 均为 0。 对于 40% 的数据，满足 1 <= n <= 1000，除起点终点外有且仅有一个 a_i=1。 对于 100% 的数据，满足 1 <= n <= 1000。 对于所有数据保证起点和终点的 a_i=1。

输入输出样例

输入样例1：

5
1 0 1 0 1

输出样例1：

2

输入样例2：

5
1 1 0 0 1

输出样例2：

3