#include <stdio.h>
#include <malloc.h>
#define FIN "algsort.in"
#define FOUT "algsort.out"

void read(int *&arr, int &n){

     FILE *fin;
     int i;

     fin = fopen(FIN, "r"); 

     fscanf(fin, "%d\n", &n);

     arr = (int*)malloc(sizeof(int) * n); 

     for(i = 0; i < n; ++i) fscanf(fin, "%d ", &arr[i]);

     fclose( fin ); 
}

void shellsort(int *arr, int n){

     int gaps,gap,i,j,temp;

     for(gaps = n/2; gaps > 0; gaps/=2) {

         gap = gaps;

         for(i = gap; i < n; ++i) {

             temp = arr[ i ];

             for(j = i - gap; (j >= 0 && arr[ j ] > temp); j-=gap) {

                 arr[ j + gap ] = arr[ j ];

             }

                 arr[ j + gap ] = temp;
         }  
     } 
}


void write(int *arr, int n){

     int i;

     FILE *fout;

     fout = fopen(FOUT, "w");

     for(i = 0; i < n; ++i) fprintf(fout, "%d ", arr[i]);

     fclose( fout ); 

}

int main() {

 int *arr, 
      n;

 read(arr,n);
 shellsort(arr,n);
 write(arr,n);

 return(0);
};