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