← 返回题目列表

Codeforces · 207/B3

B3. 军事训练

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

ABBYY 的智能海狸开始与国防部合作。现在他们训练士兵移动装甲纵队。训练包括测试一种可以传输信息的新型坦克。为了检验新型坦克,训练中有一个专门的演练,其实质如下。

最初,该列由 n 个罐组成,按照列中从开始到结束的位置顺序依次编号为 1 到 n。 During the whole exercise, exactly n messages must be transferred from the beginning of the column to its end.

Transferring one message is as follows. The tank that goes first in the column transmits the message to some tank in the column.收到消息的坦克将其进一步发送到纵队。 The process is continued until the last tank receives the message.可能并非纵队中的所有坦克都会收到该消息 - 纵队中的最后一个坦克应该收到该消息,这一点很重要。

最后一个坦克(坦克号n)收到消息后,移动到列的开头,并以相同的方式向列的末尾发送另一条消息。当消息到达最后一个坦克(坦克号 n - 1)时,该坦克移动到列的开头,并将下一条消息发送到列的末尾,依此类推。因此,当纵队中的坦克恢复到原来的顺序时,即1号坦克移动到纵队的开头后,演习就完成了。

如果坦克最初按照 1, 2, ..., n 的顺序放置在列中,那么在第一条消息之后,它们的顺序将更改为 n, 1, ..., n - 1,在第二条消息之后,它会更改为 n - 1, n, 1, ..., n - 2,依此类推。

The tanks are constructed in a very peculiar way. The tank with number i is characterized by one integer ai, which is called the message receiving radius of this tank.

在两个坦克之间传输消息需要一秒钟,但是,并不总是一个坦克可以向另一个坦克传输消息。让我们考虑列中的两个水箱,其中第一个是从头开始计数的列中的第 i 个,第二个是列中的第 j 个,并假设第二个水箱的编号为 x。 Then the first tank can transmit a message to the second tank if i < j and i ≥ j - ax.

The Ministry of Defense (and soon the Smart Beaver) faced the question of how to organize the training efficiently. The exercise should be finished as quickly as possible. We'll neglect the time that the tanks spend on moving along the column, since improving the tanks' speed is not a priority for this training.

You are given the number of tanks, as well as the message receiving radii of all tanks.您必须帮助智能海狸以一种使所有消息的总传输时间尽可能短的方式组织消息的传输。

输入

The first line contains integer n — the number of tanks in the column.接下来的 n 行中的每一行都包含一个整数 ai (1 ≤ ai ≤ 250000, 1 ≤ i ≤ n) - 按照从储罐 1 到储罐 n 的顺序排列的储罐的消息接收半径(让我们提醒您,最初储罐按编号升序排列在列中)。

To get the full points for the first group of tests it is sufficient to solve the problem with 2 ≤ n ≤ 300.

To get the full points for the second group of tests it is sufficient to solve the problem with 2 ≤ n ≤ 10000.

To get the full points for the third group of tests it is sufficient to solve the problem with 2 ≤ n ≤ 250000.

输出

打印一个整数——传输消息的最小可能总时间。

请不要使用 %lld 说明符在 С++ 中读取或写入 64 位整数。最好使用 cin、cout 流或 %I64d 说明符。

示例

输入 #1

3
2
1
1

输出 #1

5

输入 #2

5
2
2
2
2
2

输出 #2

10

注意

在第一个示例中,坦克的原始顺序是 1, 2, 3。第一个坦克向第二个坦克发送一条消息,然后第二个坦克将其发送给第三个坦克 - 需要两秒钟。第三个坦克移动到列的开头,现在坦克的顺序是 3、1、2。第三个坦克向第一个坦克发送一条消息,然后第一个坦克将其发送给第二个坦克 — 这又需要两秒钟。第二个坦克移动到开头,坦克的顺序现在是2、3、1。这样安排后,第二个坦克可以立即向第一个坦克发送消息,因为第一个坦克的消息接收半径足够大——需要一秒钟。最后,坦克恢复原来的顺序 1、2、3。总共需要 5 秒钟。

在第二个示例中,所有五个坦克都是相同的,发送一条消息需要 2 秒,因此练习总共需要 10 秒。