Shell Sort

Shell Sort

Shell Sort is a generalization of Insertion Sort to arrange a list of $n$ elements $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])

A function shellSort(A, n) performs a function insertionSort(A, n, g), which considers every $g$-th elements. Beginning with large values of $g$, it repeats the insertion sort with smaller $g$.

Your task is to complete the above program by filling ?. Write a program which reads an integer $n$ and a sequence $A$, and prints $m$, $G_i (i = 0, 1, ..., m − 1)$ in the pseudo code and the sequence $A$ in ascending order. The output of your program must meet the following requirements:

• $1 \leq m \leq 100$
• $0 \leq G_i \leq n$
• cnt does not exceed $\lceil n^{1.5}\rceil$

Constraints

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

Input

In the first line, an integer $n$ is given. In the following $n$ lines, $A_i (i=0,1,...,n-1)$ are given for each line.

Output

In the first line, print an integer $m$. In the second line, print $m$ integers $G_i (i=0,1,...,m-1)$ separated by single space character in a line. In the third line, print cnt in a line. In the following $n$ lines, print $A_i (i=0,1,...,n-1)$ respectively.

This problem has multiple solutions and the judge will be performed by a special validator.

Examples

Input

5 5 1 4 3 2

Output

2 4 1 3 1 2 3 4 5

Input

3 3 2 1

Output

1 1 3 1 2 3

inputFormat

outputFormat

output of your program must meet the following requirements:

• $1 \leq m \leq 100$
• $0 \leq G_i \leq n$
• cnt does not exceed $\lceil n^{1.5}\rceil$

Constraints

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

Input

In the first line, an integer $n$ is given. In the following $n$ lines, $A_i (i=0,1,...,n-1)$ are given for each line.

Output

In the first line, print an integer $m$. In the second line, print $m$ integers $G_i (i=0,1,...,m-1)$ separated by single space character in a line. In the third line, print cnt in a line. In the following $n$ lines, print $A_i (i=0,1,...,n-1)$ respectively.

This problem has multiple solutions and the judge will be performed by a special validator.

Examples

Input

5 5 1 4 3 2

Output

2 4 1 3 1 2 3 4 5

Input

3 3 2 1

Output

1 1 3 1 2 3

样例

5
5
1
4
3
2

2
4 1
3
1
2
3
4
5

</p>