有n个点，编号为1~n。在编号为i的点可以跳到编号为[max(i-xi,1),min(i+xi,n)]的点。

定义两个点i,j的距离为min(从i跳到j的最小步数，从j跳到i的最小步数)。你需要找到距离最大的两个点，输出它们之间的距离。

【输入数据】 第一行一个整数n。第二行n个整数x1~xn。

【输出数据】 一行一个整数表示答案。

example:

【样例输入1】

8

7 1 1 1 1 1 1 7

【样例输出1】

3

【样例输入2】

10

2 2 1 2 2 1 2 2 1 2

【样例输出2】

6

【数据范围】 对于20%的数据，n<=100。

对于40%的数据，n<=5000。

对于60%的数据，n<=30000。

对于80%的数据，n<=50000。

对于100%的数据，1<=n<=100000，1<=xi<n。