#Pmp111. 5.最远距离

5.最远距离

5.最远距离

题目描述

$有n个点,编号为1~n。在编号为的i点可以跳到编号为[max(i-x_i,1),min(i+x_i,n)]的点。 定义两个点i,j的距离为min(从i跳到j的最小步数,从j跳到i的最小步数)。你需要找到距离最大的两个点,输出它们之间的距离。$

输入格式

第一行一个整数n。第一行一个整数n。

第二行n个整数x1 xn。第二行n个整数x_1 ~ x_n。

输出格式

一行一个整数表示答案。

数据范围

(原站未提供,导入后需人工补齐)

样例

8 
7 1 1 1 1 1 1 7
3
10 
2 2 1 2 2 1 2 2 1 2 
6 

提示

对于20%的数据,n<=100。n<=100。

对于40%的数据,n<=5∗103。n<=5*10^3。

对于60%的数据,n<=3∗104。n<=3*10^4。

对于80%的数据,n<=5∗104。n<=5*10^4。

对于100%的数据,1<=n<=105,1<=xi<=n。1<=n<=10^5,1<=x_i<=n。