CF1032G.Chattering

There are $n$ parrots standing in a circle. Each parrot has a certain level of respect among other parrots, namely $r_i$. When a parrot with respect level $x$ starts chattering, $x$ neighbours to the right and to the left of it start repeating the same words in 1 second. Their neighbours then start repeating as well, and so on, until all the birds begin to chatter.

You are given the respect levels of all parrots. For each parrot answer a question: if this certain parrot starts chattering, how many seconds will pass until all other birds will start repeating it?

有 $n$ 只鹦鹉围成一个圆圈站立。每只鹦鹉在其他鹦鹉中具有一定的受尊敬程度，记为 $r_i$。当一只受尊敬程度为 $x$ 的鹦鹉开始聒噪时，它左右两侧各 $x$ 只邻居将在 1 秒后开始重复相同的词语。接着，这些邻居的邻居也将在下一秒开始重复，依此类推，直到所有鹦鹉都开始聒噪。

给定所有鹦鹉的受尊敬程度。对每只鹦鹉回答如下问题：若该鹦鹉率先开始聒噪，则需经过多少秒，其余所有鹦鹉才会开始重复它的话语？

In the first line of input there is a single integer $n$, the number of parrots ($1 \leq n \leq 10^5$).

In the next line of input there are $n$ integers $r_1$, ..., $r_n$, the respect levels of parrots in order they stand in the circle ($1 \leq r_i \leq n$).

输入的第一行包含一个整数 $n$，表示鹦鹉的数量（$1 \leq n \leq 10^5$）。

输入的第二行包含 $n$ 个整数 $r_1$, ..., $r_n$，表示按顺时针方向围成一圈的鹦鹉的尊重度（$1 \leq r_i \leq n$）。

Print $n$ integers. $i$-th of them should equal the number of seconds that is needed for all parrots to start chattering if the $i$-th parrot is the first to start.

输出 $n$ 个整数。其中第 $i$ 个整数应等于：若第 $i$ 只鹦鹉最先开始鸣叫，则所有鹦鹉都开始鸣叫所需的秒数。