You are given a permutation$$$^\dagger$$$ $$$a$$$ of size $$$n$$$. We call an index $$$i$$$ good if $$$a_i=i$$$ is satisfied. After each second, we rotate all indices that are not good to the right by one position. Formally,
For each $$$i$$$ from $$$1$$$ to $$$n$$$, find the first time that index $$$i$$$ becomes good.
$$$^\dagger$$$ A permutation is an array consisting of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$ in arbitrary order. For example, $$$[2,3,1,5,4]$$$ is a permutation, but $$$[1,2,2]$$$ is not a permutation ($$$2$$$ appears twice in the array) and $$$[1,3,4]$$$ is also not a permutation ($$$n=3$$$ but there is $$$4$$$ in the array).
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.
The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 10^6$$$) — the size of permutation $$$a$$$.
The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$) — the elements of permutation $$$a$$$.
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^6$$$.
For each test case, output a single line containing $$$n$$$ integers where the $$$i$$$-th integer represents the first time that index $$$i$$$ becomes good.
253 2 4 1 562 1 4 6 5 3
1 0 1 1 0 2 1 2 1 0 1
In the first test case, $$$2$$$ and $$$5$$$ are already in the correct position so indices $$$2$$$ and $$$5$$$ become good at $$$0$$$ second. After $$$1$$$ second, a cyclic shift will be done with $$$s=[1, 3, 4]$$$, resulting in array $$$a=[1, 2, 3, 4, 5]$$$. Notice that indices $$$1$$$, $$$3$$$ and $$$4$$$ become good at $$$1$$$ second.
In the second test case, $$$5$$$ is already in the correct position, so index $$$5$$$ becomes good at $$$0$$$ second. After $$$1$$$ second, a cyclic shift will be done with $$$s=[1, 2, 3, 4, 6]$$$, resulting in array $$$a=[3, 2, 1, 4, 5, 6]$$$. Notice that indices $$$2$$$, $$$4$$$ and $$$6$$$ become good at $$$1$$$ second. After $$$2$$$ seconds, a cyclic shift will be done with $$$s=[1, 3]$$$, resulting in array $$$a=[1, 2, 3, 4, 5, 6]$$$. Notice that indices $$$1$$$ and $$$3$$$ become good at $$$2$$$ second.
Name |
---|