第8章：数组8.16（选做）插入排序

题目描述

插入排序（Insertion Sort）。用函数编程实现在一个按升序排序的数组中查找x应插入的位置，将x插入数组中，使数组元素仍按升序排列。

输入说明

输入有3行。第一行输入1个数n表示插入前数组元素个数。第2行输入数组各元素的值，两数之间用空格隔开。第3行输入带插入的元素x的值。

输出说明

插入元素x后的各数组元素。

样例

输入

5
1 3 5 7 9
4

输出

1 3 4 5 7 9