P9199 "GMOI R2-T2" Cat-Eared Xiao

**The difference between this problem and the [enhanced version](https://www.luogu.com.cn/problem/P9202) is the Constraints and the output format. In this version, $n\le 5\times 10^3$, and the value range is $5\times 10^3$. You do not need to output the construction.** 

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 arbitrary **natural numbers**, so 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. $\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$.

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 term of the sequence.

Output one integer in one line, representing the minimum number of elements to modify.

**Sample Explanation** One possible way is to change $\{1,0,1,3,0\}$ into $\{1,1,1,3,2\}$, modifying a total of two elements. It can be proven that no better solution exists. --- **This problem uses Subtask bundled testdata.** | Subtask | $n\le$ | $k\le$ | $a_i\le$ | Special Property | Corresponding Test Points | Total Score | | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | | $0$ | $6$ | $6$ | $6$ | $-$ | $1\sim 2$ | $10$ | | $1$ | $100$ | $5\times 10^3$ | $5\times 10^3$ | $-$ | $3\sim 5$ | $20$ | | $2$ | $5\times 10^3$ | $1$ | $5\times 10^3$ | $-$ | $6\sim 10$ | $20$ | | $3$ | $5\times 10^3$ | $5\times 10^3$ | $5\times 10^3$ | $\bf A$ | $11\sim 15$ | $20$ | | $4$ | $5\times 10^3$ | $5\times 10^3$ | $5\times 10^3$ | $-$ | $16\sim 20$ | $30$ | Special Property $\bf A$: It is guaranteed that $a_i < k$. For $100\%$ of the testdata, $1\le n\le 5\times 10^3$, $0\le k,a_i\le 5\times 10^3$. Translated by ChatGPT 5