Avoiding Contiguous Subarray MEX Equal to k

Little R, a cute cat‑eared girl, loves researching the concept of the mex of sequences. Recall that for a sequence \(S\) of natural numbers the mex is defined as the smallest natural number missing from \(S\). For instance, \(\operatorname{mex}\{1,2,3\}=0\), \(\operatorname{mex}\{0,1,3\}=2\), and \(\operatorname{mex}\{0,1,2\}=3\).

Now, Little R has a sequence \(a\) of length \(n\) and she dislikes the integer \(k\). She wants to modify some elements of \(a\) (each modified element can be changed to any natural number) so that for every non‑empty contiguous subarray of \(a\), its mex is never equal to \(k\).

Observe that a contiguous subarray will have \(\operatorname{mex}=k\) if and only if it does not contain \(k\) and it contains every number in \(\{0,1,2,\ldots,k-1\}\). For \(k=0\), note that any subarray missing \(0\) would have \(\operatorname{mex}=0\).

Your task is to compute the minimum number of modifications needed to achieve the goal.

Hint: For \(k>0\), one valid strategy is to entirely remove (i.e. modify every occurrence of) at least one number in \(\{0,1,\ldots,k-1\}\) from the sequence. For \(k=0\), you must ensure that every contiguous subarray contains \(0\), so the optimal solution is to change every element that is not \(0\) into \(0\).

The answer is 0 if there is some \(d \in \{0,1,\ldots,k-1\}\) that does not occur anywhere in \(a\) (for \(k>0\)). Otherwise, for \(k>0\) the answer is \(\min_{d\in\{0,1,\ldots,k-1\}}(\text{frequency}(d))\), and for \(k=0\) the answer is \(n - \text{frequency}(0)\).

inputFormat

The first line contains two integers \(n\) and \(k\).

The second line contains \(n\) space‑separated natural numbers \(a_1, a_2, \ldots, a_n\) representing the sequence.

\(1 \le n \le 10^5\) (or as specified by the problem constraints) and the \(a_i\) are natural numbers.

outputFormat

Output a single integer — the minimum number of modifications needed so that there is no contiguous subarray whose mex is \(k\).

sample

5 2
0 1 0 1 0

2