描述

直接插入排序法是按顺序依次向前比较插入，当数据量大时，效率较低，比较耗时，在查找要插入的位置时，可以使用二分法查找，即折半查找，可以提高效率。 就是在已经排好序的数中找到新元素的位置时，用二分法来查找。

输入n个数，用插入排序将n个数按从小到大的顺序输出(n<=10000)。

输入

二行，第一行是一个整数n，为要排序的整数数量；第二行是n个整数，两数之间以空格分隔。

输出

一个n个整数，为排序后的整数，两数之间以空格分隔。

样例输入

10

1 4 3 2 9 7 18 22  23 3

样例输出

1 2 3 3 4 7 9 18 22 23