Problem B: 赛车游戏

Problem B: 赛车游戏

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 451  Solved: 85
[Submit] [Status] [Web Board] [Creator:]

Description

一条赛道上有n个停车点,每个停车点都有一辆车,第i辆车可以最多行驶a[i]个停车点。
PIPI可以在任意一个停车点换车,问PIPI最少换几次车可以到达终点(第n个停车点)。

Input

多组输入。
第一行输入停车点数量n(1<=n<=100000)。
第二行输入n个整数,代表第i辆车最多可以行驶a[i]个停车点(1<=a[i]<=1000)。

Output

对于每组输入,输出到达终点的最少换车次数。

Sample Input

5
2 3 1 1 4
3
3 2 1

Sample Output

1
0