For a permutation p1,p2,…,pN of 1…N (1≤N≤2⋅105), let f(p)=
. 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≤T≤105) independent tests. Each test is specified as follows:
The first line contains N.
The second line contains p1,p2,…,pN (1≤pi≤N), which is guaranteed to be a permutation of 1…N.
It is guaranteed that the sum of N over all tests does not exceed 106 .
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≤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 p3 and p4, 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 q1 two steps forward, q is good.
It can be seen that the other two cyclic shifts are not good.
SCORING:
Input 2: N≤10
Inputs 3-5: T≤10,N≤2000
Inputs 6-11: No additional constraints.
Problem credits: Akshaj Arora