{"problem":{"name":"「GMOI R2-T2」猫耳小","description":{"content":"小 R 是一个可爱的猫耳女孩子，她喜欢研究数列的 $\\operatorname{mex}\\text{*}$。 现在她有一个长度为 $n$ 的数列 $a$。她讨厌整数 $k$，因此她希望修改数列 $a$ 的若干个元素为任意**自然数**，使得 $a$ 的任意**连续非空子串**的 $\\operatorname{mex}$ 都不等于 $k$。 请你求出最少需要修改多少个元素。 $\\text{*}","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":131072},"difficulty":{"LuoguStyle":"P3"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9199"},"statements":[{"statement_type":"Markdown","content":"小 R 是一个可爱的猫耳女孩子，她喜欢研究数列的 $\\operatorname{mex}\\text{*}$。\n\n现在她有一个长度为 $n$ 的数列 $a$。她讨厌整数 $k$，因此她希望修改数列 $a$ 的若干个元素为任意**自然数**，使得 $a$ 的任意**连续非空子串**的 $\\operatorname{mex}$ 都不等于 $k$。\n\n请你求出最少需要修改多少个元素。\n\n$\\text{*}$ 本题中，数列的 $\\operatorname{mex}$ 被定义为数列中最小未出现的**自然数**，例如：\n\n- $\\operatorname{mex}\\{1,2,3\\}=0$，因为 $0$ 是自然数。\n- $\\operatorname{mex}\\{0,1,3\\}=2$。\n- $\\operatorname{mex}\\{0,1,2\\}=3$。\n\n## Input\n\n第一行两个整数 $n,k$，表示数列长度和小 R 讨厌的数。\n\n第二行 $n$ 个整数，第 $i$ 个整数为 $a_i$，表示这个数列的第 $i$ 项。\n\n## Output\n\n一行一个整数，表示最少需要修改的元素个数。\n\n[samples]\n\n## Background\n\n**本题与 [加强版](https://www.luogu.com.cn/problem/P9202) 的区别在于数据范围和输出格式。在这一版本中，$n\\le 5\\times 10^3$，值域为 $5\\times 10^3$，你不需要给出构造。**\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/r8a6ylx3.png)\n\n## Note\n\n**样例解释**\n\n一种方案是将 $\\{1,0,1,3,0\\}$ 改为 $\\{1,1,1,3,2\\}$，共改动两个元素。\n\n可以证明不存在更优的方案。\n\n---\n\n**本题使用 Subtask 捆绑测试。**\n\n| Subtask | $n\\le$ | $k\\le$ | $a_i\\le$ | 特殊性质 | 对应测试点 | 总分 |\n| :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: |\n| $0$ | $6$ | $6$ | $6$ | $-$ | $1\\sim 2$ | $10$ |\n| $1$ | $100$ | $5\\times 10^3$ | $5\\times 10^3$ | $-$ | $3\\sim 5$ | $20$ |\n| $2$ | $5\\times 10^3$ | $1$ | $5\\times 10^3$ | $-$ | $6\\sim 10$ | $20$ |\n| $3$ | $5\\times 10^3$ | $5\\times 10^3$ | $5\\times 10^3$ | $\\bf A$ | $11\\sim 15$ | $20$ |\n| $4$ | $5\\times 10^3$ | $5\\times 10^3$ | $5\\times 10^3$ | $-$ | $16\\sim 20$ | $30$ |\n\n特殊性质 $\\bf A$：保证 $a_i < k$。\n\n对于 $100\\%$ 的数据，$1\\le n\\le 5\\times 10^3$，$0\\le k,a_i\\le 5\\times 10^3$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9199","tags":["贪心","洛谷原创","O2优化","构造","洛谷月赛"],"sample_group":[["5 2\n1 0 1 3 0","2"]],"created_at":"2026-03-03 11:09:25"}}