CF207B2.Military Trainings

The Smart Beaver from ABBYY started cooperating with the Ministry of Defence. Now they train soldiers to move armoured columns. The training involves testing a new type of tanks that can transmit information. To test the new type of tanks, the training has a special exercise, its essence is as follows.

Initially, the column consists of n tanks sequentially numbered from 1 to n in the order of position in the column from its beginning to its end. 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 tank which received the message sends it further down the column. The process is continued until the last tank receives the message. It is possible that not all tanks in the column will receive the message — it is important that the last tank in the column should receive the message.

After the last tank (tank number n) receives the message, it moves to the beginning of the column and sends another message to the end of the column in the same manner. When the message reaches the last tank (tank number n - 1), that tank moves to the beginning of the column and sends the next message to the end of the column, and so on. Thus, the exercise is completed when the tanks in the column return to their original order, that is, immediately after tank number 1 moves to the beginning of the column.

If the tanks were initially placed in the column in the order 1, 2, ..., n, then after the first message their order changes to n, 1, ..., n - 1, after the second message it changes to n - 1, n, 1, ..., n - 2, and so on.

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

Transferring a message between two tanks takes one second, however, not always one tank can transmit a message to another one. Let's consider two tanks in the column such that the first of them is the i-th in the column counting from the beginning, and the second one is the j-th in the column, and suppose the second tank has number x. Then the first tank can transmit a message to the second tank if i < j and i ≥ j - a__x.

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. You must help the Smart Beaver and organize the transferring of messages in a way that makes the total transmission time of all messages as small as possible.

ABBYY 的智能海狸开始与国防部合作，训练士兵行进装甲纵队。训练中包含对一种新型坦克的测试，这种坦克能够传输信息。为测试该新型坦克，训练中设计了一项特殊演习，其核心内容如下：

初始时，纵队由 $n$ 辆坦克组成，按从纵队前端到末端的顺序依次编号为 $1$ 至 $n$。在整个演习过程中，必须恰好传递 $n$ 条消息，每条消息均从纵队前端传至末端。

单条消息的传递过程如下：位于纵队最前端的坦克将消息发送给纵队中的某辆坦克；收到消息的坦克再将消息继续向纵队后方传递；该过程持续进行，直至纵队末端的坦克接收到该消息。注意，并非纵队中所有坦克都必须接收该消息——关键在于纵队末端的坦克必须最终接收到该消息。

当末端坦克（编号为 $n$）接收到消息后，它立即移动至纵队前端，并以同样方式发送下一条消息至纵队末端。当该消息抵达新的末端坦克（编号为 $n-1$）时，该坦克也移动至纵队前端并发送下一条消息；依此类推。整个演习在纵队中所有坦克恢复初始排列顺序时结束，即编号为 $1$ 的坦克移动至纵队前端之后立即结束。

若坦克初始排列顺序为 $1,\,2,\,\dots,\,n$，则第一条消息传递完毕后，纵队顺序变为 $n,\,1,\,\dots,\,n-1$；第二条消息传递完毕后，顺序变为 $n-1,\,n,\,1,\,\dots,\,n-2$；以此类推。

这些坦克的构造极为特殊。编号为 $i$ 的坦克具有一个整数参数 $a_i$，称为该坦克的消息接收半径。

两辆坦克之间传递一条消息耗时 1 秒；但并非任意两辆坦克之间均可直接通信。考虑纵队中两辆坦克：第一辆位于从纵队前端起第 $i$ 位，第二辆位于第 $j$ 位，且第二辆坦克编号为 $x$。则第一辆坦克可向第二辆坦克发送消息，当且仅当满足 $i < j$ 且 $i \ge j - a_x$。

国防部（以及即将参与其中的智能海狸）面临的问题是：如何高效组织此次训练？目标是使整个演习尽快完成。我们忽略坦克在纵队中移动所耗费的时间，因为提升坦克行驶速度并非本次训练的优先事项。

现给定坦克总数 $n$，以及每辆坦克的消息接收半径 $a_i$。你需协助智能海狸，规划消息传递路径，使得所有 $n$ 条消息的总传输时间最小化。

The first line contains integer n — the number of tanks in the column. Each of the next n lines contains one integer a__i (1 ≤ a__i ≤ 250000, 1 ≤ i ≤ n) — the message receiving radii of the tanks in the order from tank 1 to tank n (let us remind you that initially the tanks are located in the column in ascending order of their numbers).

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.

第一行包含一个整数 $n$ —— 列中坦克的数量。接下来的 $n$ 行每行包含一个整数 $a_i$（$1 \leq a_i \leq 250000$，$1 \leq i \leq n$），表示从第 1 辆坦克到第 $n$ 辆坦克的消息接收半径（请注意：初始时，坦克按编号升序排列在列中）。

若要获得第一组测试用例的全部分数，只需解决满足 $2 \leq n \leq 300$ 的情形即可。

若要获得第二组测试用例的全部分数，只需解决满足 $2 \leq n \leq 10000$ 的情形即可。

若要获得第三组测试用例的全部分数，只需解决满足 $2 \leq n \leq 250000$ 的情形即可。

Print a single integer — the minimum possible total time of transmitting the messages.

Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.

输出一个整数——传输所有消息所需的最小总时间。

请注意，在 C++ 中不要使用 %lld 说明符读取或写入 64 位整数。推荐使用 cin、cout 流，或 %I64d 说明符。

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.

在第一个样例中，坦克的初始排列顺序为 $1,\ 2,\ 3$。第一辆坦克向第二辆坦克发送消息，随后第二辆坦克再将消息转发给第三辆坦克——耗时两秒。接着，第三辆坦克移动至队列最前端，此时坦克排列顺序变为 $3,\ 1,\ 2$。第三辆坦克向第一辆坦克发送消息，随后第一辆坦克再将消息转发给第二辆坦克——又耗时两秒。然后，第二辆坦克移动至队列最前端，此时坦克排列顺序变为 $2,\ 3,\ 1$。在此排列下，第二辆坦克可立即向第一辆坦克发送消息，因为第一辆坦克的消息接收半径足够大——仅需一秒。最后，坦克恢复至原始排列顺序 $1,\ 2,\ 3$。整个演习共耗时 $5$ 秒。

在第二个样例中，全部五辆坦克完全相同，且发送单条消息均需两秒，因此整个演习共耗时 $10$ 秒。