#2231. 跳石头大赛

跳石头大赛

题目描述

一年一度的《跳石头》大赛又要开始了!

这项比赛将在一条笔直的河道中进行,河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终点。

包含起点和终点在内,一共有 NN 块岩石,其中 11 号石头是起点,NN 号石头是终点,并且任意相邻两个编号的石头之间的距离都是 11

在比赛过程中,选手们将从起点出发,每一步跳向相邻的岩石,直至到达终点即可获胜

为了提高比赛难度,组委会计划标记一些岩石,选手们在比赛过程中不允许跳到被标记的岩石上。

现在浩然为了准备《跳石头》大赛,提前开始锻炼自己的跳跃能力

假设浩然的跳跃能力为 xx,那么他每次可以 最多 跳跃 xx 的距离

即可以从 ii 号岩石一步跳到 i+1i+xi+1 \sim i+x 中的任意一块岩石

现在浩然想知道,他至少要把跳跃能力锻炼到多少,才能保证获胜?

输入格式

输入第一行包含一个正整数 nn,表示岩石数量。

输入第二行包含 nn 个正整数 aia_i 表示编号为 ii 的岩石是否被标记,若 ai=0a_i=0 则这块石头被主办方标记,ai=1a_i=1 则没有被标记

输出格式

输出一个整数,表示浩然至少需要的跳跃能力

数据范围

对于 20%20\% 的数据,满足 1n501 \leq n \leq 50,除起点终点外所有 aia_i 均为 00

对于 40%40\% 的数据,满足 1n10001 \leq n \leq 1000,除起点终点外有且仅有一个 ai=1a_i=1

对于 100%100\% 的数据,满足 1n10001 \leq n \leq 1000

对于所有数据保证起点和终点的 ai=1a_i=1

输入样例1

5
1 0 1 0 1

输出样例1

2

输入样例2

5
1 1 0 0 1

输出样例2

3