#include <stdio.h>
#define N 200000

int main()
{
  int i, j, n, k=0;
  int A[N], B[N], C[N];
  scanf("%d",&n);
  for(i = 0 ; i < n ; i++)
    {
      scanf("%d",&A[i]);
    }
  for(i = 0 ; i < n ; i++)
    {
      if(A[i] > k)   k = A[i];
    }

  for(j = 0 ; j < n ; j++)
    {
      C[A[j]]++;
    }

  for(i = 1 ; i < k + 1 ; i++)
    {
      C[i] = C[i] + C[i-1];
    }

 for(i = 0 ; i < n ; i++)
    {
      printf("%d",C[i]);
    }
 printf("\n");
  for(j = n - 1; j > - 1; j--)
    {
      B[C[A[j]]] = A[j];
      C[A[j]]--;
    }

  for(i = 1 ; i < n + 1 ; i++)
    {
      if(i == n){
	printf("%d\n",B[i]);
      }else{
	printf("%d ",B[i]);
	}
    }
  return 0;
}