P15576 [USACO26FEB] Good Cyclic Shifts G

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.

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$.

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

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