Background

The difference between this problem and the original problem is the constraints and the output format. In this version, $n\le 10^6$ and the value range is $10^9$. You need to output a construction.

Problem Description

Little R is a cute cat-eared girl. She likes studying the $\operatorname{mex}\text{*}$ of sequences.

Now she has a sequence $a$ of length $n$. She hates the integer $k$, so she wants to modify some elements of $a$ into any natural numbers, such that the $\operatorname{mex}$ of every non-empty contiguous subarray of $a$ is not equal to $k$.

Please find the minimum number of elements that need to be modified, and output one valid plan.

$\text{*}$ In this problem, the $\operatorname{mex}$ of a sequence is defined as the smallest natural number that does not appear in the sequence. For example:

• $\operatorname{mex}\{1,2,3\}=0$, because $0$ is a natural number.
• $\operatorname{mex}\{0,1,3\}=2$.
• $\operatorname{mex}\{0,1,2\}=3$.

Input Format

The first line contains two integers $n,k$, representing the length of the sequence and the number that Little R hates.

The second line contains $n$ integers. The $i$-th integer is $a_i$, representing the $i$-th element of the sequence.

Output Format

The first line contains one integer, representing the minimum number of modified elements.

The second line contains $n$ integers, representing the modified sequence. You need to ensure that every number in the modified sequence is within $[0,10^9]\cap\Z$.

5 2
1 0 1 3 0

2
1 1 1 3 2

Hint

Explanation of the sample

One possible plan is to change $\{1,0,1,3,0\}$ into $\{1,1,1,3,2\}$, modifying $2$ elements in total.

It can be proven that no better plan exists.

Scoring

This problem uses a special judge (Special Judge) for evaluation.

For each test point, if your minimum number of steps is correct, you can get $30\%$ of the score. Based on this, if your construction is also correct, you can get full marks.

Note: Even if you cannot output a construction, you still need to output $n$ integers on the second line according to the output format.

This problem uses bundled tests, with no subtasks.

For $100\%$ of the testdata, $1\le n\le 10^6$, $0\le k,a_i\le 10^9$.

The I/O volume of this problem is large, so it is recommended to use fast I/O methods.

Translated by ChatGPT 5