Robot Doc is located in the hall, with n computers stand in a line, numbered from left to right from 1 to n. Each computer containsexactly one piece of information, each of which Doc wants to get eventually. The computers are equipped with a security system, so to crack the i-th of them, the robot needs to collect at least ai any pieces of information from the other computers. Doc can hack the computer only if he is right next to it.
The robot is assembled using modern technologies and can move along the line of computers in either of the two possible directions, but the change of direction requires a large amount of resources from Doc. Tell the minimum number of changes of direction, which the robot will have to make to collect all n parts of information if initially it is next to computer with number 1.
It is guaranteed that there exists at least one sequence of the robot's actions, which leads to the collection of all information. Initially Doc doesn't have any pieces of information.
The first line contains number n (1 ≤ n ≤ 1000). The second line contains n non-negative integers a1, a2, ..., an (0 ≤ ai < n), separated by a space. It is guaranteed that there exists a way for robot to collect all pieces of the information.
Print a single number — the minimum number of changes in direction that the robot will have to make in order to collect all n parts of information.
3 0 2 0
1
5 4 2 3 0 1
3
7 0 3 1 0 5 2 6
2
In the first sample you can assemble all the pieces of information in the optimal manner by assembling first the piece of information in the first computer, then in the third one, then change direction and move to the second one, and then, having 2 pieces of information, collect the last piece.
In the second sample to collect all the pieces of information in the optimal manner, Doc can go to the fourth computer and get the piece of information, then go to the fifth computer with one piece and get another one, then go to the second computer in the same manner, then to the third one and finally, to the first one. Changes of direction will take place before moving from the fifth to the second computer, then from the second to the third computer, then from the third to the first computer.
In the third sample the optimal order of collecting parts from computers can look like that: 1->3->4->6->2->5->7.
题目大意：有n台电脑排成一行，每台电脑有一个属性值$a_i$表示至少要拥有$a_i$个信息才能破解它，破解一台电脑可以获得一条信息（不会消耗信息）。一个机器人现在一条信息也没有，站在第一台电脑旁边，面朝右。要破解一台电脑必须站在这台电脑旁边，机器人只能向前移动，如果向后转身则需要消耗能量，但移动不用消耗能量。求机器人最少要转身多少次才能破解完所有的电脑。输入信息保证有解。
显然这样一定是最优的：在1~n之间不停地来回移动（从1走到n，再从n回到1，……），走到电脑旁时能破解就破解，直到所有电脑都破解完了。
代码在此。
评论 (0)
