给你一个大小为 $$$n$$$ 的排列$$$^\dagger$$$ $$$a$$$。如果满足 $$$a_i=i$$$ ,我们称索引 $$$i$$$ 好。每一秒之后,我们将所有不好的索引向右旋转一个位置。正式地,
- 令 $$$s_1,s_2,\ldots,s_k$$$ 为 $$$a$$$ 的索引,这些索引不适合按升序排列。也就是说,$$$s_j < s_{j+1}$$$,如果索引$$$i$$$不好,则存在$$$j$$$使得$$$s_j=i$$$。
- 对于从$$$1$$$到$$$k$$$的每个$$$i$$$,我们一次性分配$$$a_{s_{(i \% k+1)}} := a_{s_i}$$$。
对于从 $$$1$$$ 到 $$$n$$$ 的每个 $$$i$$$,找到索引 $$$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$$$ 第一次变好。
示例
输入 #1
2 5 3 2 4 1 5 6 2 1 4 6 5 3
输出 #1
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$$$ 第二位变得更好。