4912.希尔排序

## 题目描述

希尔排序$(Shell Sort)$是插入排序$(Insertion Sort)$的一种推广算法，用于对包含$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))$通过调用插入排序函数$(insertionSort(A, n, g))$来实现，该函数会对每隔$g$个元素进行排序。算法从较大的$g$值开始，逐步减小$g$值并重复进行插入排序。

你的任务是完善上述程序，补全?处的代码。并请编写一个程序：

1. 读取整数$n$和一个序列$A$

2. 输出伪代码中的$m$和$G_i(i=0,1,...,m-1)$

3. 输出升序排列后的序列$A$

程序输出需满足以下要求：

1. $1\lem\le100$

2. $0\leG_i\len$

3. 排序操作总次数$cnt$不超过$\lceiln^{1.5}\rceil$

## 输入格式

第一行为一个整数$n$，表示元素个数。接下来的$n$行中，每行给出一个元素$A_i（i=0,1,...,n-1）$。

## 输出格式

输出格式要求：

1. 第一行输出整数$m$

2. 第二行输出$m$个整数$G_i(i=0,1,...,m-1)$，每个数之间用单个空格隔开

3. 第三行输出$cnt$值

4. 接下来的$n$行，按顺序输出排序后的$A_i(i=0,1,...,n-1)$

补充说明：

1. $G_i$表示希尔排序中使用的间隔(gap)序列

2. $cnt$表示实际执行的元素比较和交换操作总次数

## 数据范围

- $1\len\le1,000,000$
- $0\leA_i\le10^9$

## 输入
```in1
5
1
4
3
2
```

## 输出
```out1
2
4 1
3
1
2
3
4
5
```

```in2
3
2
1
```

```in2
1
3
1
2
3
```