G. Болтовня
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

$$$n$$$ попугаев стоят по кругу. У каждого попугая есть некоторый уровень уважения среди остальных попугаев, обозначаемый $$$r_i$$$. Если попугай с уровнем уважения $$$x$$$ начинает болтовню, то через одну секунду его $$$x$$$ cоседей слева и справа начинают повторять за ним. Естественно, слыша болтовню, их соседи также включаются в процесс, и так далее, пока все попугаи не начнут болтать.

Вам даны уровни уважения всех попугаев. Для каждого попугая независимо ответьте на вопрос: если данный попугай начнёт болтать, через сколько секунд все остальные попугаи начнут повторять за ним?

Входные данные

В первой строке задано целое число $$$n$$$ — количество попугаев ($$$1 \leq n \leq 10^5$$$).

В следующей строке задано $$$n$$$ целых чисел $$$r_1$$$, ..., $$$r_n$$$ — уровни уважения попугаев в том порядке, в котором они стоят в кругу ($$$1 \leq r_i \leq n$$$).

Выходные данные

Выведите $$$n$$$ чисел. $$$i$$$-е из них должно равняться количеству секунд, которое пройдёт между тем, как $$$i$$$-й попугай начнёт болтать, и тем, когда заболтают все попугаи в кругу.

Примеры
Входные данные
4
1 1 4 1
Выходные данные
2 2 1 2
Входные данные
8
1 2 2 1 5 1 3 1
Выходные данные
3 3 2 2 1 2 2 3