Chèn vào mảng tăng đã cho để vẫn tăng (Insert into a Strictly Increasing Array)

Nguồn: Phước Hưng OJ

Phiên bản: Phước Hưng OJ Extended

Đề bài

Cho mảng số nguyên tăng nghiêm ngặt

$$a_0<a_1<\cdots<a_{n-1}$$

và số nguyên $x$ không trùng với bất kỳ phần tử nào của mảng.

Hãy chèn $x$ vào mảng để thu được mảng mới $b$ có $n+1$ phần tử và vẫn tăng nghiêm ngặt.

Đặt

$$p=\min\left(\{i\mid 0\le i<n,\ a_i>x\}\cup\{n\}\right).$$

Khi đó $x$ phải được chèn tại chỉ số $p$; các phần tử từ $p$ trở đi của mảng cũ dịch sang phải một vị trí.

Hãy in kích thước mới và mảng kết quả.

Input

Dòng đầu chứa hai số nguyên $n$ và $x$. Dòng thứ hai chứa $n$ số nguyên tăng nghiêm ngặt $a_0,a_1,\ldots,a_{n-1}$.

Output

Dòng đầu in $n+1$. Dòng thứ hai in mảng sau khi chèn $x$.

Subtask

Subtask 1 (100 điểm): $1\le n<2\cdot10^5$; $|a_i|,|x|\le10^9$; $a_i<a_{i+1}$; $x\ne a_i$ với mọi $i$.

Ví dụ

Input

5 6
1 3 5 8 10

Output

6
1 3 5 6 8 10

Giải thích

Phần tử đầu tiên lớn hơn $6$ là $8$ ở chỉ số $3$, nên $p=3$. Chèn $6$ trước $8$ cho mảng vẫn tăng nghiêm ngặt.