CF207B1.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$ 秒。