CF1896E Permutation Sorting

给定一个长度为 $n$ 的排列 $a$。我们称下标 $i$ 是“好”的，如果满足 $a_i = i$。每经过一秒钟，我们将所有不是“好”的下标对应的元素整体向右轮转一位。具体来说： - 设 $s_1, s_2, \ldots, s_k$ 是所有不是“好”的下标，按从小到大排列。即 $s_j < s_{j+1}$，且如果下标 $i$ 不是“好”的，则存在 $j$ 使得 $s_j = i$。 - 对于每个 $i$ 从 $1$ 到 $k$，同时执行 $a_{s_{(i \bmod k)+1}} := a_{s_i}$。 对于每个 $i$ 从 $1$ 到 $n$，求出下标 $i$ 第一次变为“好”的时刻。 $^\dagger$ 排列是指由 $1$ 到 $n$ 的 $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$ 已经在正确的位置，因此下标 $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$ 秒变为“好”。 由 ChatGPT 4.1 翻译