Background

The difference between this problem and the enhanced version 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.

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 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$.

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

Output Format

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

5 2
1 0 1 3 0

2

Hint

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.

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