\(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
2000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач