E. Permutation Sorting
data structures; sortings
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, Let \(s_1,s_2,\ldots,s_k\) be the indices of \(a\) that are not good in increasing order. That is, \(s_j < s_{j+1}\) and if index \(i\) is not good, then there exists \(j\) such that \(s_j=i\). For each \(i\) from \(1\) to \(k\), we assign \(a_{s_{(i \% k+1)}} := a_{s_i}\) all at once. 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.
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.