Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

G. Chattering

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputThere 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

Codeforces (c) Copyright 2010-2019 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Mar/20/2019 07:04:05 (d3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|