Shell Sort

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

def insertion_sort(N, A, g):
    global cnt
    for i in range(g, N):
        v = A[i]
        j = i - g
        while j >= 0 and A[j] > v:
            A[j + g] = A[j]
            j -= g
            cnt += 1
        A[j + g] = v

def shell_sort(N, A, G):
    cnt = 0
    m = ?
    G = [?, ?, ..., ?]
    for i in G:
        insertion_sort(N, A, G[i])

shell_sort(N, A) は、一定の間隔 $g$ だけ離れた要素のみを対象とした挿入ソートである insertion_sort(N, A, 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 \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

Note

Algorithm

 

---