Avoiding MEX Equals k in All Subsegments

Little R is a cute cat‐eared girl who loves to study the mex operation. She has a sequence a of length n and she hates the integer k. Therefore, she wants to modify a number of elements in the sequence (each modified element can be set to any natural number, i.e. any nonnegative integer) so that for every nonempty contiguous subarray, its mex is not equal to k.

The mex of a sequence is defined as the smallest natural number (i.e. nonnegative integer) that does not appear in it. For example:

• \(\operatorname{mex}\{1,2,3\}=0\), because \(0\) is the smallest natural number missing.
• \(\operatorname{mex}\{0,1,3\}=2\).
• \(\operatorname{mex}\{0,1,2\}=3\).

Please determine the minimum number of modifications required and provide one valid plan (i.e. a final modified sequence) such that no contiguous subarray has a mex equal to \(k\).

Note: A contiguous subarray is formed by taking a continuous segment from the sequence.

Hint: Observe that a subarray’s mex equals \(k\) if and only if it contains every number in \(\{0,1,\dots,k-1\}\) but does not contain \(k\). Thus, a sufficient way to avoid such subarrays is to ensure that in the final sequence at least one number from \(\{0,1,\dots,k-1\}\) is completely missing. In other words, if there exists some \(x\) in \(\{0,1,\dots,k-1\}\) that does not appear in the final sequence, then no subarray can have its mex equal to \(k\).

One optimal strategy is as follows:

• If \(k=0\): A subarray’s mex is \(0\) if it does not contain \(0\). Hence, every subarray must contain \(0\). The only solution is to change every element that is not \(0\) to \(0\).
• If \(k>0\): Check if there is already some number in \(\{0, 1, \dots, k-1\}\) missing from the original sequence. If yes, then the requirement is already met and no modification is needed. Otherwise, for each \(x\) in \(\{0, 1, \dots, k-1\}\), count its frequency, and choose the \(x\) with minimum frequency. Then, change every occurrence of that \(x\) into \(k\). The final sequence will then not contain \(x\) at all, and every subarray will be missing \(x\), ensuring its mex is not \(k\) (it will be at most \(x\)).

Input and Output formats are described below.

inputFormat

The first line contains two integers n and k (\(0 \le k \le 10^9\)). The second line contains n space‐separated integers \(a_1, a_2, \dots, a_n\) (each \(a_i\) is a natural number).

outputFormat

Output two lines. The first line contains a single integer: the minimum number of modifications. The second line contains the final sequence of n space‐separated integers after modifications. If there are several solutions, print any one of them.

sample

5 0
0 1 0 2 0

2
0 0 0 0 0