#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#define NMAX 100

int n = 10;
void swap(int *p, int *q) {
	int tmp = *p;
	*p = *q;
	*q = tmp;
}


void print(FILE *g, int *v, int n) {
	int i;
	for (i =  1; i <= n; i++) {
		fprintf(g, "%d%c", v[i] , (i<n? ' ' : '\n' ));
	}
}

int partition(int *v, int p, int q) {
	int pivot = v[p + rand() % (q-p+1)];
	int i = p-1, j = q+1;
	while (i < j) {
		// from left half find first element >= pivot
		while (v[++i] < pivot);
		// from right half last element <= pivot
		while (v[--j] > pivot);
		if (i < j) {
			swap(&v[i], &v[j]);
		} else {
			// i >= j
			return j;
		}
	}
}

void insertionSort(int *v, int n) {
	int i, j;
	for (i = 2; i<= n; i++) {
		
		int pivot = v[i];
		int j = i - 1;
		while ( j >= 1 && v[j] > pivot) {
			v[j+1] = v[j];
			j--;
		}
		v[j+1] = pivot;
	}
}

int main() {
	FILE *f = fopen("algsort.in", "r");
	FILE *g = fopen("algsort.out", "w");

	srand(time(NULL));

	int n, *v,i;
	fscanf(f,"%d", &n);
	v = (int *)malloc((n+1) * sizeof(int));
	
	for (i =  1; i <= n; i++) {
		fscanf(f,"%d", &v[i]);
	}
	insertionSort(v, n);
	print(g, v, n);
	free(v);
	return 0;
}