#include <iostream>
#include<fstream>
#include <cmath>
using namespace std;


int v[10000001],smen[100000],n,lsmen;

void ordoneaza_partitie(int sm)
{
    int aux;
    for(int i=(sm-1)*lsmen+1;i<n && i <sm*lsmen; i++)
        for(int j=i;j<=n && j<= sm*lsmen;j++)
            if(v[i]>v[j])
    {
        aux=v[i];
        v[i]=v[j];
        v[j]=aux;
    }
}
int c[10000001];
void merge_partitie(int i,int imax,int j, int jmax)
{

  //  int i=(sm1-1)*lsmen+1;
  //  int j=(sm2-1)*lsmen+1;
  //  int imax=sm1*lsmen<n?sm1*lsmen:n;
   // int jmax=sm2*lsmen<n?sm2*lsmen:n;
    int k=1;

    while(i<=imax&&i<=n&&j<=jmax&&j<=n)
    {
        if(v[i]<v[j]) c[k++]=v[i++];
        else c[k++]=v[j++];
    }
    while(i<=imax&&i<=n)
        c[k++]=v[i++];
    while(j<=imax&&j<=n)
        c[k++]=v[j++];

    for(int z=1;z<k;z++)
        v[z]=c[z];

}

int main()
{
    ifstream f("algsort.in");
    ofstream g("algsort.out");
    f>>n;
    lsmen=ceil(sqrt(n));
    //cout<<lsmen<<'\n';
    int csmen=0,ismen=1,pastismen=1;
    for(int i=1;i<=n;i++)
    {
        f>>v[i];
    }

    for(int sm=1;sm<=lsmen;sm++)
        for(int i=sm*lsmen-lsmen+2;i<=n&&i<=sm*lsmen;i++)
    {
        if(v[i]<v[i-1])
            smen[sm]=1;
    }

    for(int sm=1;sm<=lsmen;sm++)
        if(smen[sm])
            ordoneaza_partitie(sm);

    for(int sm=1;sm<lsmen;sm++)
        merge_partitie(1,sm*lsmen,sm*lsmen+1,(sm+1)*lsmen);

     for(int i=1;i<=n;i++)
        g<<v[i]<<" ";
    //cout<<endl;
    //for(int i=1;i<=lsmen;i++)
      //  cout<<smen[i]<<" ";
  f.close();
  g.close();
    return 0;
}