题目背景

希蒙在学习插入排序了。。。。。

题目描述

给定一个n$(1 \le n \le 5 \times 10^6)$个元素的单调不下降有序序列，在序列中插入一个整数，使得新的序列依然有序。

格式

输入格式

三行

第一行，一个整数 n

第二行，n个有序整数

第三行，待插入的整数x

输出格式

两行

第一行， x 应该插入的位置

第二行，n+1个整数，插入x后的新的数组

样例

5
1 3 3 4 5
2

2
1 2 3 3 4 5

3
1 3 3 
1

2
1 1 3 3

数据范围

n$(1 \le n \le 5 \times 10^6)$

$0 \le x,a[i] \le 10000$