Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official. ×

G. Chattering
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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?

Input

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$).

Output

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.

Examples
Input
4
1 1 4 1

Output
2 2 1 2

Input
8
1 2 2 1 5 1 3 1

Output
3 3 2 2 1 2 2 3