#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

const int N=1e5+10;

int n,a[N];

void print1()
{
    int b[N];
    memcpy(b,a,sizeof a);
    stable_sort(b,b+n);
    for(int i=0;i<n;i++)
    cout<<b[i]<<" ";
    puts("");
}

/*
8 1 4 3 8 8 9
*/

void print2()
{
    int b[N];
    memcpy(b,a,sizeof a);
    int d=5;
    for(int i=0;i<n;i++)
    {
        int x=b[i];
        int j;
        for(j=i-d;j>=0&&b[j]>b[i];j-=d)
        b[j+d]=b[j];
        b[j+d]=x;
    }
    for(int i=0;i<n;i++)
    cout<<b[i]<<" ";
    puts("");
}

void print3()
{
    int b[N];
    memcpy(b,a,sizeof a);
    sort(b,b+n);
    for(int i=0;i<n;i++)
    cout<<b[i]<<" ";
    puts("");
}

void print4()
{
    int b[N];
    memcpy(b,a,sizeof a);
    sort(b,b+n);
    for(int i=0;i<n;i++)
    cout<<b[i]<<" ";
    puts("");
}

void pr...