ZUFEOJ Home ProblemSet Source/Category Contest Status Ranklist F.A.Qs ContestProblemSetList
Login Register

问题 A: 机器人黑客

内存限制：256 MB 时间限制：1 S
题面：传统 评测方式：文本比较 上传者：
提交：140 通过：82
返回比赛提交提交记录

题目描述

有 n 台电脑排成一排，每个电脑里面有一条信息，某机器人要黑掉所有的电脑。黑掉一台电脑即可获取当前这台电脑的信息， 机器人要想黑掉第 i 台电脑，则至少需要先获得黑掉第i台电脑需要的 ai 条信息（只有获得的信息数量大于等于ai,才能黑掉第i台电脑）。这位机器人每次会从 1 走到 n 再从 n 走到 1 ，问他最少需要转几次弯（掉几次头）可以黑掉所以电脑。

输入格式

第一行包含数字n ( 1<=n<=1000).第二行包含n个非负整数a1，a2······an( 0<=ai<n ），用空格分隔。保证机器人有办法收集所有信息。

输出格式

打印单个数字 — 机器人为了收集所有数字而必须进行的方向更改的最小次数n部分信息.


Examples
Input 
3
0 2 0
Output 
1
Input 
5
4 2 3 0 1
Output 
3
Input 
7
0 3 1 0 5 2 6
Output 
2
注意
在第一个样本中，第一台电脑、第三台需要0条信息可以直接黑，如此获得了2条信息；然后改变方向并移动到第2台电脑处，黑第2台电脑需要2条信息，正好。
在第二个样本中，第4台计算机需要0条信息，可以直接黑；并获取该信息，然后用一条计算机转到第5台计算机并获取另一条，然后以相同的方式转到第2台计算机，然后转到第3台计算机，最后， 到第一个。方向的改变将在从第五台计算机移动到第二台计算机之前发生，然后从第二台计算机移动到第三台计算机，然后从第三台计算机移动到第一台计算机。
在第三个样本中，从计算机收集零件的最佳顺序如下所示：1->3->4->6->2->5->7。

输入样例 复制 

3
0 2 0

输出样例 复制 

1

分类标签