Description

N个元素组成，排好序的数组，往数组中插入一个数K。数字K插入到数组中第一个大于它的元素前（如果没有则插入到数组末尾）。

Format

Input

第一行，一个整数N（N<=10000），表示数组元素个数；

第二行，N个整数，表示数组元素；

第三行，一个整数K，表示插入的数字。

Output

一行，插入完成的数组。

Samples

10
1 2 3 3 4 4 5 6 7 8
3

1 2 3 3 3 4 4 5 6 7 8

Limitation

1s, 1024KiB for each test case.