import java.util.Scanner;
class ShellSort {
public static void main
(String args
[]) {
Scanner in
= new Scanner
(System.
in); //taking input
int n = in.nextInt();
int a[] = new int[n];
for(int i=0;i<n;i++)
{
a[i] = in.nextInt();
}
//shell sort algorithm
//outer loop for gap
//inner loop for insertion sort
for(int gap = n/2;gap>0;gap = gap/2)
{
//insertion sort of indexes 0 gap 2*gap 3*gap ... n
//insertion sort of indexes 1 1+gap 1+2*gap 1+3*gap ... n
//
//
//insertion sort of indexes gap-1 2*gap-1 ...n
for(int i=gap;i<n;i++)
{
int temp = a[i];
int j;
for(j=i; j>=gap && temp<a[j-gap];j = j-gap)
{
a[j] = a[j-gap];
}
a[j] = temp;
}
}
for(int i=0;i<n;i++)
}
}
aW1wb3J0IGphdmEudXRpbC5TY2FubmVyOwoKCmNsYXNzIFNoZWxsU29ydCB7CgoJcHVibGljIHN0YXRpYyB2b2lkIG1haW4oU3RyaW5nIGFyZ3NbXSkKCXsKCQlTY2FubmVyIGluID0gbmV3IFNjYW5uZXIoU3lzdGVtLmluKTsKCQkvL3Rha2luZyBpbnB1dAoJCWludCBuID0gaW4ubmV4dEludCgpOwoJCWludCBhW10gPSBuZXcgaW50W25dOwoJCWZvcihpbnQgaT0wO2k8bjtpKyspCgkJewoJCQlhW2ldID0gaW4ubmV4dEludCgpOwoJCX0KCQkvL3NoZWxsIHNvcnQgYWxnb3JpdGhtCgkJLy9vdXRlciBsb29wIGZvciBnYXAKCQkvL2lubmVyIGxvb3AgZm9yIGluc2VydGlvbiBzb3J0CgkJZm9yKGludCBnYXAgPSBuLzI7Z2FwPjA7Z2FwID0gZ2FwLzIpCgkJewoJCQkvL2luc2VydGlvbiBzb3J0IG9mIGluZGV4ZXMgMCBnYXAgMipnYXAgMypnYXAgLi4uIG4KCQkJLy9pbnNlcnRpb24gc29ydCBvZiBpbmRleGVzIDEgMStnYXAgMSsyKmdhcCAxKzMqZ2FwIC4uLiBuCgkJCS8vCgkJCS8vCgkJCS8vaW5zZXJ0aW9uIHNvcnQgb2YgaW5kZXhlcyBnYXAtMSAyKmdhcC0xIC4uLm4KCQkJZm9yKGludCBpPWdhcDtpPG47aSsrKQoJCQl7CgkJCQlpbnQgdGVtcCA9IGFbaV07CgkJCQlpbnQgajsKCQkJCWZvcihqPWk7IGo+PWdhcCAmJiB0ZW1wPGFbai1nYXBdO2ogPSBqLWdhcCkKCQkJCXsKCQkJCQlhW2pdID0gYVtqLWdhcF07CgkJCQl9CgkJCQlhW2pdID0gdGVtcDsKCQkJfQoJCX0KCQlmb3IoaW50IGk9MDtpPG47aSsrKQoJCQlTeXN0ZW0ub3V0LnByaW50bG4oYVtpXSk7Cgl9Cn0K