Дана перестановка\(^\dagger\) \(a\) длины \(n\). Назовем индекс \(i\) хорошим, если \(a_i=i\). После каждой секунды мы циклически сдвигаем все индексы, которые не являются хорошими, вправо на одну позицию. Формально,
- Пусть \(s_1,s_2,\ldots,s_k\) — индексы \(a\), которые являются нехорошими в порядке возрастания. То есть \(s_j < s_{j+1}\) и если индекс \(i\) не является хорошим, то существует \(j\) такой, что \(s_j=i\).
- Для каждого \(i\) от \(1\) до \(k\) мы одновременно назначаем \(a_{s_{(i \% k+1)}} := a_{s_i}\).
Для каждого \(i\) от \(1\) до \(n\) найдите первый момент времени, когда индекс \(i\) становится хорошим.
\(^\dagger\) Перестановкой является массив, состоящий из \(n\) различных целых чисел от \(1\) до \(n\) в произвольном порядке. Например, \([2,3,1,5,4]\) — перестановка, но \([1,2,2]\) не перестановка (\(2\) встречается в массиве дважды) и \([1,3,4]\) тоже не перестановка (\(n=3\), но в массиве встречается \(4\)).
Выходные данные
Для каждого набора входных данных выведите одну строку, содержащую \(n\) целых чисел, где \(i\)-е целое число равняется первому моменту времени, когда индекс \(i\) становится хорошим.
Примечание
В первом наборе входных данных \(2\) и \(5\) уже находятся на правильных позициях, поэтому индексы \(2\) и \(5\) становятся хорошими в момент времени \(0\). Через \(1\) секунду будет выполнен циклический сдвиг с \(s=[1, 3, 4]\), в результате чего будет получен массив \(a=[1, 2, 3, 4, 5]\). Обратите внимание, что индексы \(1\), \(3\) и \(4\) становятся хорошими на \(1\) секунде.
Во втором наборе входных данных \(5\) уже находится на правильной позиции, поэтому индекс \(5\) становится хорошим на \(0\) секунде. Через \(1\) секунду будет выполнен циклический сдвиг с \(s=[1, 2, 3, 4, 6]\), в результате чего будет получен массив \(a=[3, 2, 1, 4, 5, 6]\). Обратите внимание, что индексы \(2\), \(4\) и \(6\) становятся хорошими через \(1\) секунду. Через \(2\) секунды будет выполнен циклический сдвиг с \(s=[1, 3]\), в результате чего будет получен массив \(a=[1, 2, 3, 4, 5, 6]\). Обратите внимание, что индексы \(1\) и \(3\) становятся хорошими на \(2\) секунде.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
5
3 2 4 1 5
6
2 1 4 6 5 3
|
1 0 1 1 0
2 1 2 1 0 1
|