Problem 1. Good Cyclic Shifts

USACO 2026 Third Contest, Gold

For a permutation $p_1,p_2,\dots,p_N$ of $1\dots N$ ($1\le N\le 2\cdot 10^5$), let $f(p)=\sum_{i=1}^N \frac{|p_i-i|}{2}$. A permutation is

good

if it can be turned into the identity permutation using at most $f(p)$ swaps of adjacent elements.

Given a permutation, find which cyclic shifts of it are good.

INPUT FORMAT (input arrives from the terminal / stdin):

The input consists of $T$ ($1\le T\le 10^5$) independent tests. Each test is specified as follows:

The first line contains $N$.

The second line contains $p_1,p_2,\dots,p_N$ ($1\le p_i\le N$), which is guaranteed to be a permutation of $1\dots N$.

It is guaranteed that the sum of $N$ over all tests does not exceed $10^6$.

OUTPUT FORMAT (print output to the terminal / stdout):

For each test, output two lines:

On the first line, output the number of good cyclic shifts $k$.

Then output a line with $k$ space-separated integers $s$ ($0\le s<N$) in increasing order, meaning that $p$ is good when cyclically shifted to the right $s$ times.

SAMPLE INPUT:

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

SAMPLE OUTPUT:

0

2
0 1
5
0 1 2 3 4

Consider the second test case, where $p = [1, 2, 4, 3]$.

• $f(p) = (|1 - 1| + |2 - 2| + |4 - 3| + |3 - 4|) / 2 = 1$. Since $p$ can be turned into the identity permutation in one move by swapping $p_3$ and $p_4$, $p$ is good.
• Cyclically shifting $p$ to the right $1$ time, we get $q = [3, 1, 2, 4]$. $f(q) = (|3 - 1| + |1 - 2| + |2 - 3| + |4 - 4|) / 2 = 2$. Since $q$ can be turned into the identity permutation in two moves by swapping $q_1$ two steps forward, $q$ is good.

It can be seen that the other two cyclic shifts are not good.

SCORING: Input 2: $N\le 10$Inputs 3-5: $T\le 10, N\le 2000$Inputs 6-11: No additional constraints.

Problem credits: Akshaj Arora