CF583B Robot's Task

机器人 Doc 位于大厅中，那里有 $n$ 台计算机依次排列，从左到右编号为 $1$ 到 $n$。每台计算机都包含一条信息，Doc 最终都想获得这些信息。这些计算机配备了安全系统，因此要破解第 $i$ 台计算机，机器人必须已经从其他计算机中获得至少 $a_{i}$ 条任意信息。Doc 只能在紧挨着目标计算机时才能破解它。 该机器人采用了现代技术，可以沿计算机排列方向任意移动，但每次改变移动方向都需要消耗大量资源。请你计算，为了获得全部 $n$ 条信息，机器人最少需要改变多少次移动方向。初始时，机器人在第 $1$ 台计算机旁边，没有获得任何信息。 保证至少存在一种操作顺序可以让机器人收集到所有信息。最初 Doc 没有任何信息。

第一行包含一个整数 $n$（$1 \le n \le 1000$）。 第二行包含 $n$ 个非负整数 $a_1, a_2, \ldots, a_n$（$0 \le a_i < n$），用空格分隔。保证机器人存在收集完全部信息的操作顺序。

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

在第一个样例中，可以采用最优方式：首先在第一台计算机获得信息，然后到第三台获得信息，之后改变方向移动到第二台获得信息，最后在已经拥有两条信息的情况下，获得最后一台的信息。 在第二个样例中，为了最优收集全部信息，Doc 可以先一直走到第四台计算机获得信息，再到第五台获得信息，然后回到第二台获得信息，接下来到第三台，最后到第一台。方向改变发生在从第五台移动到第二台，从第二台到第三台，以及从第三台到第一台之前。 在第三个样例中，收集顺序最优可以为：1→3→4→6→2→5→7。 由 ChatGPT 5 翻译