Good Cyclic Shifts | Code Joint

For a permutation $p_{1}, p_{2}, \dots, p_{N}$ of $1 \dots N$ ( $1 \leq N \leq 2 \cdot 1 0^{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.

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 \leq 10$
Inputs 3-5: $T \leq 10, N \leq 2000$
Inputs 6-11: No additional constraints.

Problem credits: Akshaj Arora

Source: USA Computing Olympiad.

Input Format

The input consists of $T$ ( $1 \leq T \leq 1 0^{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 \leq p_{i} \leq 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 $1 0^{6}$ .

Output Format

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 \leq 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

Submit

Language