정렬

어린 P는 셸 정렬(shell sort) 알고리즘을 막 배웠다. 그는 $N$개의 정수로 이루어진 배열을 오름차순으로 정렬하려는 코드를 작성했다. 정렬할 배열을 $A$라고 하자.

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);

여기서 i, N, X, gap, temp, ok는 모두 정수이다(C/C++의 int 타입).

그런데 코드를 입력하던 중 어린 P는 11번째 줄(if (gap/2 > 1) gap=gap/2; else gap=1;)을 빠뜨리고 말았다. 이 줄이 없으므로 gap은 절대 줄어들지 않고 처음 값 X를 그대로 유지하며, 반복문은 한 번의 패스에서 교환이 한 번도 일어나지 않을 때까지 같은 간격의 패스를 계속 반복한다.

정렬할 배열 $A$가 주어진다. $A$의 원소 $N$개는 모두 서로 다르며, 각각 $1$ 이상 $N$ 이하이다.

11번째 줄이 빠진 이 알고리즘이 그래도 $A$를 올바르게 정렬하는 모든 $X$ 값을 구하여라. 이러한 $X$ 값을 유효한(valid) 값이라고 부른다.

첫째 줄에 정수 $N$이 주어진다.

둘째 줄에 배열 $A$를 나타내는 $N$개의 정수가 공백 하나로 구분되어 주어진다.

첫째 줄에 유효한 $X$ 값의 개수를 출력한다.

둘째 줄에 유효한 모든 $X$ 값을 오름차순으로 공백 하나로 구분하여 출력한다.

• $1 < N < 500000$
• $1 \le X \le N-1$
• $A$는 $1, 2, \dots, N$의 순열이다(모든 원소가 서로 다르다).

예를 들어 $N = 6$, $A = [4, 2, 6, 1, 5, 3]$인 경우 유효한 $X$ 값은 다음과 같다.

• $X = 1$: 다음 위치 쌍에서 교환이 일어난다 — $(1,2), (3,4), (4,5), (5,6), (2,3), (4,5), (1,2), (3,4)$.
• $X = 3$: 다음 위치 쌍에서 교환이 일어난다 — $(1,4), (3,6)$.