题目描述

有一个有序数字序列，从小到大排序，将一个新输入的数插入到序列中，保证插入新数后，序列仍然是升序。

输入格式

第一行输入一个整数 $N。$

第二行输入 $N$ 个升序排列的整数，输入用空格分隔的 $N$ 个整数。

第三行输入想要进行插入的一个整数。

输出格式

输出为一行，$N+1$ 个有序排列的整数。

数据范围

$1 ≤ n ≤ {10}^5$

$1 ≤ 序列中的整数≤ {10}^5$

输入样例：

5
1 6 9 22 30
8

输出样例：

1 6 8 9 22 30