P9199 「GMOI R2-T2」猫耳小
题目背景
**本题与 [加强版](https://www.luogu.com.cn/problem/P9202) 的区别在于数据范围和输出格式。在这一版本中，$n\le 5\times 10^3$，值域为 $5\times 10^3$，你不需要给出构造。**
题目描述
小 R 是一个可爱的猫耳女孩子，她喜欢研究数列的 $\operatorname{mex}\text{*}$。
现在她有一个长度为 $n$ 的数列 $a$。她讨厌整数 $k$，因此她希望修改数列 $a$ 的若干个元素为任意**自然数**，使得 $a$ 的任意**连续非空子串**的 $\operatorname{mex}$ 都不等于 $k$。
请你求出最少需要修改多少个元素。
$\text{*}$ 本题中，数列的 $\operatorname{mex}$ 被定义为数列中最小未出现的**自然数**，例如：
- $\operatorname{mex}\{1,2,3\}=0$，因为 $0$ 是自然数。
- $\operatorname{mex}\{0,1,3\}=2$。
- $\operatorname{mex}\{0,1,2\}=3$。
输入格式
无
输出格式
无
说明/提示
**样例解释**
一种方案是将 $\{1,0,1,3,0\}$ 改为 $\{1,1,1,3,2\}$，共改动两个元素。
可以证明不存在更优的方案。
---
**本题使用 Subtask 捆绑测试。**
| Subtask | $n\le$ | $k\le$ | $a_i\le$ | 特殊性质 | 对应测试点 | 总分 |
| :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: |
| $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$ |
特殊性质 $\bf A$：保证 $a_i < k$。
对于 $100\%$ 的数据，$1\le n\le 5\times 10^3$，$0\le k,a_i\le 5\times 10^3$。