CF583B.Robot's Task

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 contains exactly 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 a__i 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.

机器人 Doc 位于机房中，有 $n$ 台计算机排成一行，从左到右依次编号为 $1$ 到 $n$。每台计算机中恰好存储一条信息，而 Doc 最终需要获取全部 $n$ 条信息。这些计算机配备了安全系统：要破解第 $i$ 台计算机，机器人必须已掌握其余计算机中的至少 $a_i$ 条信息。Doc 仅当紧邻某台计算机时，才能对其进行入侵。

该机器人采用现代技术制造，可沿计算机排列的直线向两个方向之一移动；但每次改变移动方向都会消耗 Doc 大量资源。请计算 Doc 在初始位置位于第 $1$ 号计算机旁的前提下，为获取全部 $n$ 条信息所需进行的最小方向改变次数。

题目保证至少存在一种操作序列，使得 Doc 能成功收集全部信息。初始时 Doc 尚未掌握任何信息。

The first line contains number n (1 ≤ n ≤ 1000). The second line contains n non-negative integers _a_1, _a_2, ..., a__n (0 ≤ a__i < n), separated by a space. It is guaranteed that there exists a way for robot to collect all pieces of the information.

第一行包含一个整数 $n$（$1 \leq n \leq 1000$）。第二行包含 $n$ 个非负整数 $a_1,\,a_2,\,\dots,\,a_n$（$0 \leq a_i < n$），以空格分隔。题目保证机器人存在一种方式收集全部信息碎片。

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.

输出一个整数——机器人为了收集全部 $n$ 个信息片段所需改变方向的最少次数。

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.

在第一个样例中，你可以通过以下最优方式整合所有信息：首先在第一台计算机上获取信息，然后在第三台计算机上获取信息，接着改变方向前往第二台计算机，此时已拥有 2 份信息，最后再收集最后一份信息。

在第二个样例中，为以最优方式收集全部信息，Doc 可以先前往第四台计算机获取一份信息，然后前往第五台计算机（此时携带 1 份信息）再获取一份，接着以同样方式前往第二台计算机，再前往第三台计算机，最后前往第一台计算机。方向变换分别发生在从第五台计算机移向第二台计算机之前、从第二台计算机移向第三台计算机之前，以及从第三台计算机移向第一台计算机之前。

在第三个样例中，从各台计算机收集信息的最优顺序可能如下：1→3→4→6→2→5→7。