Sorting

Little P has just learned the shell sort algorithm. He wrote code that is meant to sort an array of $N$ integers into ascending order. Let $A$ be the array to be sorted.

gap = X;
do
{  ok = 1;
   for (i = 1; i<= N - gap; i++)
      if (A[i] > A[i+gap])
        {  temp = A[i];
           A[i] = A[i+gap];
           A[i+gap] = temp;
           ok = 0;
        }
   if (gap/2 > 1) gap=gap/2; else gap=1;
}  while (ok == 0);

Here i, N, X, gap, temp, and ok are integers (the int type in C/C++).

While typing the code, Little P forgot to copy line 11 (the line if (gap/2 > 1) gap=gap/2; else gap=1;). Because that line is missing, gap is never reduced: it keeps its initial value X for the whole run, so the loop just repeats the same fixed-gap pass over and over until an entire pass makes no swaps.

You are given the array $A$. It has $N$ distinct elements, each between $1$ and $N$.

Find every value of $X$ for which this algorithm (with line 11 missing) still sorts $A$ correctly. We call such values of $X$ valid.

The first line contains one integer $N$.

The second line contains $N$ integers separated by single spaces, describing the array $A$.

On the first line, print the number of valid values of $X$.

On the second line, print all valid values of $X$ in ascending order, separated by single spaces.

• $1 < N < 500000$
• $1 \le X \le N-1$
• $A$ is a permutation of $1, 2, \dots, N$ (all elements are distinct).

For example, take $N = 6$ and $A = [4, 2, 6, 1, 5, 3]$. The valid values of $X$ are:

• $X = 1$: swaps happen at the position pairs $(1,2), (3,4), (4,5), (5,6), (2,3), (4,5), (1,2), (3,4)$.
• $X = 3$: swaps happen at the position pairs $(1,4), (3,6)$.