\(n\) попугаев стоят по кругу. У каждого попугая есть некоторый уровень уважения среди остальных попугаев, обозначаемый \(r_i\). Если попугай с уровнем уважения \(x\) начинает болтовню, то через одну секунду его \(x\) cоседей слева и справа начинают повторять за ним. Естественно, слыша болтовню, их соседи также включаются в процесс, и так далее, пока все попугаи не начнут болтать.
Вам даны уровни уважения всех попугаев. Для каждого попугая независимо ответьте на вопрос: если данный попугай начнёт болтать, через сколько секунд все остальные попугаи начнут повторять за ним?
Выходные данные
Выведите \(n\) чисел. \(i\)-е из них должно равняться количеству секунд, которое пройдёт между тем, как \(i\)-й попугай начнёт болтать, и тем, когда заболтают все попугаи в кругу.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
1 1 4 1
|
2 2 1 2
|
|
2
|
8
1 2 2 1 5 1 3 1
|
3 3 2 2 1 2 2 3
|