E. Сортировка перестановки
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дана перестановка$$$^\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$$$).

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 10^6$$$) — длину перестановки $$$a$$$.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$) — элементы перестановки $$$a$$$.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$10^6$$$.

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

Для каждого набора входных данных выведите одну строку, содержащую $$$n$$$ целых чисел, где $$$i$$$-е целое число равняется первому моменту времени, когда индекс $$$i$$$ становится хорошим.

Пример
Входные данные
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
Примечание

В первом наборе входных данных $$$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$$$ секунде.