← 返回题目列表

Codeforces · 583/B

B. 机器人的任务

中文机器翻译题面 查看原题

Robot Doc位于大厅,n台电脑排成一排,从左到右编号为1到n。每台计算机都包含一条信息,每一条信息都是 Doc 最终想要获取的。这些计算机配备了安全系统,因此要破解第 i 个计算机,机器人需要从其他计算机收集至少 ai 条信息。只有当博士就在计算机旁边时,他才能破解计算机。

机器人是用现代技术组装而成的,可以沿着计算机的路线向两个可能的方向之一移动,但方向的改变需要Doc.的大量资源。告诉机器人如果最初位于编号 1 的计算机旁边,则必须改变方向才能收集所有 n 部分信息。

保证至少存在一个机器人动作序列,从而收集所有信息。最初Doc没有任何信息。

输入

第一行包含数字 n (1 ≤ n ≤ 1000)。第二行包含 n 个非负整数 a1, a2, ..., an (0 ≤ ai < n),用空格分隔。保证机器人有一种方法可以收集所有信息。

输出

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

示例

输入 #1

3
0 2 0

输出 #1

1

输入 #2

5
4 2 3 0 1

输出 #2

3

输入 #3

7
0 3 1 0 5 2 6

输出 #3

2

注意

在第一个示例中,您可以通过首先在第一台计算机中组装信息片段,然后在第三台计算机中组装信息片段,然后改变方向并移动到第二台计算机,然后在拥有 2 条信息的情况下收集最后一条信息,以最佳方式组装所有信息片段。

在以最佳方式收集所有信息的第二个示例中,Doc 可以转到第四台计算机并获取该信息,然后转到第五台计算机并获取另一条信息,然后以相同的方式转到第二台计算机,然后转到第三台计算机,最后转到第一台计算机。在从第五台计算机移动到第二台计算机,然后从第二台计算机移动到第三台计算机,然后从第三台计算机移动到第一台计算机之前,将发生方向的改变。

在第三个示例中,从计算机收集零件的最佳顺序可能如下所示:1->3->4->6->2->5->7。