题目描述

有一个已经排好序的数组为1,2,3,4,5,6,7,8,9。求输入一个数后,按照原来的排序规律将它插入数组中。

输入

一个整数

输出

排序之后的数组

样例

样例 1

输入

1

输出

1 1 2 3 4 5 6 7 8 9
样例 2

输入

3

输出

1 2 3 3 4 5 6 7 8 9
样例 3

输入

6

输出

1 2 3 4 5 6 6 7 8 9