说明

对于一个 $1\dots N$ 的排列 $p_1,p_2,\dots,p_N$（$1\le N\le 2\cdot 10^5$），定义 $f(p)=\sum_{i=1}^N \frac{|p_i-i|}{2}$。如果一个排列能够通过至多 $f(p)$ 次相邻元素交换变为 $p_i=i$（恒等排列，identity permutation）的排列，则称该排列是 好的。

给定一个排列，找出它的哪些循环移位是好的。

输入格式

输入包含 $T$（$1\le T\le 10^5$）个独立的测试用例。每个测试用例的格式如下：

第一行包含 $N$。

第二行包含 $p_1,p_2,\dots,p_N$（$1\le p_i\le N$），保证是 $1\dots N$ 的一个排列。

保证所有测试用例的 $N$ 之和不超过 $10^6$。

输出格式

对于每个测试用例，输出两行：

第一行输出好的循环移位的数量 $k$。

然后输出一行，包含 $k$ 个按升序排列的整数 $s$（$0\le s<N$），表示将 $p$ 向右循环移位 $s$ 次后得到的排列是好的。

3
5
5 4 3 2 1
4
1 2 4 3
5
1 2 3 4 5

0

2
0 1
5
0 1 2 3 4

提示

考虑第二个测试用例，其中 $p = [1, 2, 4, 3]$。

• $f(p) = (|1 - 1| + |2 - 2| + |4 - 3| + |3 - 4|) / 2 = 1$。因为 $p$ 可以通过交换 $p_3$ 和 $p_4$ 一次操作变为恒等排列，所以 $p$ 是好的。
• 将 $p$ 向右循环移位 $1$ 次，得到 $q = [3, 1, 2, 4]$。$f(q) = (|3 - 1| + |1 - 2| + |2 - 3| + |4 - 4|) / 2 = 2$。因为 $q$ 可以通过将 $q_1$ 向前交换两步变为恒等排列，所以 $q$ 是好的。 可以看出另外两个循环移位不是好的。

评分标准

• 输入 2：$N\le 10$
• 输入 3-5：$T\le 10, N\le 2000$
• 输入 6-11：无额外限制。

题目来源：Akshaj Arora

翻译由 DeepSeek 完成