時間制限 : sec, メモリ制限 : KB
English / Japanese  

Shell Sort

次のプログラムは、挿入ソート(ALDS1_1_A)を応用して $n$ 個の整数を含む数列 $A$ を昇順に整列するプログラムです。

1  insertionSort(A, n, g)
2      for i = g to n-1
3          v = A[i]
4          j = i - g
5          while j >= 0 && A[j] > v
6              A[j+g] = A[j]
7              j = j - g
8              cnt++
9          A[j+g] = v
10
11 shellSort(A, n)
12     cnt = 0
13     m = ?
14     G[] = {?, ?,..., ?}
15     for i = 0 to m-1
16         insertionSort(A, n, G[i])

shellSort(A, n) は、一定の間隔 $g$ だけ離れた要素のみを対象とした挿入ソートである insertionSort(A, n, g) を、最初は大きい値から $g$ を狭めながら繰り返します。これをシェルソートと言います。

上の疑似コードの ? を埋めてこのプログラムを完成させてください。$n$ と数列 $A$ が与えられるので、疑似コード中の $m$、$m$ 個の整数 $G_i (i = 0, 1, ..., m − 1)$、入力 $A$を昇順にした列を出力するプログラムを作成してください。ただし、出力は以下の条件を満 たす必要があります。

  • $1 \leq m \leq 100$
  • $0 \leq G_i \leq n$
  • cnt の値は $\lceil n^{1.5}\rceil$ を超えてはならない

入力

1 行目に整数 $n$ が与えられます。続く $n$ 行目に $n$ 個の整数 $A_i (i=0,1,...,n-1)$ が与えられます。

出力

1 行目に整数 $m$、2 行目に $m$ 個の整数 $G_i (i=0,1,...,m-1)$ を空白区切りで出力してください。
3 行目に、$G$ を用いた場合のプログラムが終了した直後の cnt の値を出力してください。
続く $n$ 行に整列した $A_i (i=0,1,...,n-1)$ を出力してください。

この問題では、1つの入力に対して複数の解答があります。条件を満たす出力は全て正解となります。

制約

  • $1 \leq n \leq 1,000,000$
  • $0 \leq A_i \leq 10^9$

入力例 1

5
5
1
4
3
2

出力例 1

2
4 1
3
1
2
3
4
5

入力例 2

3
3
2
1

出力例 2

1
1
3
1
2
3