题目描述

给出一个已经按不降顺序排列的整数序列，再给出一个整数。把这个整数插入序列，保持新序列仍按不降顺序排列。

输入格式

第一行一个整数 $n$。第二行 $n$ 个整数。第三行是待插入的整数。

输出格式

输出插入后的 $n+1$ 个整数，以空格分隔。

样例

4
1 3 4 5
2

1 2 3 4 5

数据范围

$1\le n\le100000$；所有整数在有符号32位整数范围内，原序列不降。