CF207B1 Military Trainings

ABBYY 的聪明海狸开始与国防部合作。现在他们正在训练士兵行动装甲车队。训练包括测试一种能够传输信息的新型坦克。为了测试这种新型坦克，训练中有一个特殊的演习，其核心如下所述。 最初，车队由从 $1$ 到 $n$ 依次编号的 $n$ 辆坦克组成，按照从车队起始位置到结束位置的顺序排列。在整个演习过程中，必须准确传递 $n$ 条信息，从车队的起始位置传递到结束位置。 传递一条信息的过程如下：车队中排在第一位的坦克将信息传递给车队中的某辆坦克。接收到信息的坦克将其继续传递给车队中的下一辆坦克。这个过程一直持续到最后一辆坦克接收到信息。车队中并不是所有的坦克都会接收到信息，但最重要的是确保最后一辆坦克能够接收到信息。 当最后一辆坦克（坦克编号为 $n$）接收到信息后，它将移动到车队的起始位置，并以相同的方式将另一条信息发送到车队的末尾。当信息到达最后一辆坦克（坦克编号为 $n-1$）时，该坦克将移动到车队的起始位置，并将下一条信息发送到车队的末尾，以此类推。因此，当车队中的坦克恢复到它们的原始顺序时，即在坦克编号 $1$ 移动到车队起始位置后，演习就完成了。 如果初始时坦克按照顺序 $1, 2, ..., n$ 排列在车队中，那么在第一条信息传递后，它们的顺序变为 $2, 1, ..., n-1, n$。在第二条信息传递后，顺序变为 $n, 2, 1, ..., n-2, n-1$。以此类推，每传递一条信息，坦克的顺序都会发生变化。 这些坦克的构造方式非常独特。编号为 $i$ 的坦克具有一个整数 $a_i$，被称为该坦克的信息接收半径。 在两辆坦克之间传递一条信息需要一秒钟，然而，并不总是一辆坦克能够将信息传递给另一辆坦克。假设车队中有两辆坦克，第一辆坦克是从起始位置开始计算的第 $i$ 辆坦克，第二辆坦克是车队中的第 $j$ 辆坦克，并且假设第二辆坦克的编号是 $x$。那么，如果 $i < j$ 并且 $j - a_x \le i$，那么第一辆坦克可以将信息传递给第二辆坦克。 国防部（以及很快轮到智能海狸）面临如何高效组织训练的问题。演习应尽快完成。我们将忽略坦克在列队移动所花费的时间，因为提高坦克的速度不是这次训练的重点。 你已获得坦克的数量以及所有坦克的信息接收半径。您必须帮助智能海狸，以尽可能减少所有信息的总传输时间的方式组织信息的传递。 ### **简明题意** 对于一个 $1, 2,...,n$ 的排列，每个数有一个半径 $a_i$。每次从开头发射信号，传到末尾， 并将末尾移到队头。这样操作 $n$ 次。每次传递耗时 $1$ 秒。求总耗时最小的方案。

第一行包含一个整数 $n$，表示车队中的坦克数量。接下来的 $n$ 行中，每行包含一个整数 $a_i$ $(1 \le a_i \le 250000,1\le i\le n)$，表示坦克从第 1 辆到第 n 辆的信息接收半径（请注意，初始时坦克按照编号的升序排列在列队中）。 | 数据组号 | 数据范围 | | -------- | ------------------ | | $T1$ | $2\le n\le 300$ | | $T2$ | $2\le n\le 1000$ | | $T3$ | $2\le n\le 250000$ |

输出一个整数，表示传输信息的最小总时间。 请在 C++ 中不要使用 `%lld` 来读取或写入 $64$ 位整数。最好使用 `cin`、`cout` 流或 `%I64d` 来代替。 ### **说明/提示** 在样例一中，坦克的初始顺序是 $1, 2, 3$。第一辆坦克将信息发送给第二辆坦克，然后第二辆坦克将其发送给第三辆坦克，这需要两秒钟。第三辆坦克移动到车队的起始位置，现在坦克的顺序变为 $3, 1, 2$。第三辆坦克将信息发送给第一辆坦克，然后第一辆坦克将其发送给第二辆坦克，又花费了两秒钟。第二辆坦克移动到起始位置，坦克的顺序变为 $2, 3, 1$。在这种排列下，第二辆坦克可以立即将信息发送给第一辆坦克，因为第一辆坦克的信息接收半径足够大，只需要一秒钟。最后，坦克们恢复到初始顺序 $1, 2, 3$。总共，这个演习花费了 $5$ 秒钟。 在样例二中，所有五辆坦克都是相同的，并且发送一条消息需要两秒钟，因此总共的演习时间是 $10$ 秒钟。

In the first sample the original order of tanks is $ 1,2,3 $ . The first tank sends a message to the second one, then the second tank sends it to the third one — it takes two seconds. The third tank moves to the beginning of the column and the order of tanks now is $ 3,1,2 $ . The third tank sends a message to the first one, then the first one sends it to the second one — it takes two more seconds. The second tank moves to the beginning and the order of the tanks is now $ 2,3,1 $ . With this arrangement, the second tank can immediately send a message to the first one, since the message receiving radius of the first tank is large enough — it takes one second. Finally, the tanks return to their original order $ 1,2,3 $ . In total, the exercise takes $ 5 $ seconds. In the second sample, all five tanks are the same and sending a single message takes two seconds, so in total the exercise takes $ 10 $ seconds.