#include <stdio.h>
#include <stdlib.h>

void insertion_sort();
int main()
{
  /* read input */
  int i, j, n;
  int *A;
  scanf("%d",&n);
  A = (int *) malloc((n+1)*sizeof(int));
  printf("sort %d numbers:\n",n);
  for (i = 1; i <= n; i++) {
    scanf("%d",&j);
    A[i] = j;
    printf("%8d",A[i]);
  }
  printf("\n");

  /* sort input */
  insertion_sort(A,n);

  /* output sorted numbers */
  printf("sorted sequence:\n");
  for (i = 1; i <= n; i++) printf("%8d",A[i]);
  printf("\n");
  return 0;
}

void insertion_sort(int* A, int n)
{
  int i,j,key;
  for (j = 2; j <= n; j++) {
    key = A[j];
    /* insert A[j] into the sorted sequence A[1...j-1] */
    i = j - 1;
    while ((i > 0) && (A[i] > key) ) {
      A[i+1] = A[i];
      i--;
    }
    A[i+1] = key;
  }
}