「GMOI R2-T2」猫耳小(加强版)
题目背景
**本题与 [原题](https://www.luogu.com.cn/problem/P9199) 的区别在于数据范围和输出格式。在这一版本中,$n\le 10^6$,值域为 $10^9$,你需要给出构造。**
![](https://cdn.luogu.com.cn/upload/image_hosting/r8a6ylx3.png)
题目描述
小 R 是一个可爱的猫耳女孩子,她喜欢研究数列的 $\operatorname{mex}\text{*}$。
现在她有一个长度为 $n$ 的数列 $a$。她讨厌整数 $k$,因此她希望修改数列 $a$ 的若干个元素为任意**自然数**,使得 $a$ 的任意**连续非空子串**的 $\operatorname{mex}$ 都不等于 $k$。
请你求出最少需要修改多少个元素,并给出方案。
$\text{*}$ 本题中,数列的 $\operatorname{mex}$ 被定义为数列中最小未出现的**自然数**,例如:
- $\operatorname{mex}\{1,2,3\}=0$,因为 $0$ 是自然数。
- $\operatorname{mex}\{0,1,3\}=2$。
- $\operatorname{mex}\{0,1,2\}=3$。
输入输出格式
输入格式
第一行两个整数 $n,k$,表示数列长度和小 R 讨厌的数。
第二行 $n$ 个整数,第 $i$ 个整数为 $a_i$,表示这个数列的第 $i$ 项。
输出格式
第一行一个整数,表示最少需要修改的元素个数。
第二行 $n$ 个整数,表示修改后的数列。你需要保证修改后的数列的每个数在 $[0,10^9]\cap\Z$ 的范围内。
输入输出样例
输入样例 #1
5 2
1 0 1 3 0
输出样例 #1
2
1 1 1 3 2
说明
**样例解释**
一种方案是将 $\{1,0,1,3,0\}$ 改为 $\{1,1,1,3,2\}$,共改动两个元素。
可以证明不存在更优的方案。
---
**评分方式**
本题采用自定义校验器(Special Judge)进行评测。
对于每个测试点,如果你的最小步数正确,可以得到 $30\%$ 的分数。在此基础上,如果方案也正确,可以得到满分。
请注意:即使你不会给出方案,也请按照输出格式在第二行输出 $n$ 个整数。
---
**本题采用捆绑测试,数据无梯度。**
对于 $100\%$ 的数据,$1\le n\le 10^6$,$0\le k,a_i\le 10^9$。
本题读写量较大,建议使用效率较高的读写方式。