#1451. 「GMOI R2-T2」猫耳小

「GMOI R2-T2」猫耳小

题目描述

小 R 是一个可爱的猫耳女孩子,她喜欢研究数列的 mex⁡*\operatorname{mex}\text{*}。

现在她有一个长度为 nn 的数列 aa。她讨厌整数 kk,因此她希望修改数列 aa 的若干个元素为任意自然数,使得 aa 的任意连续非空子串的 mex⁡\operatorname{mex} 都不等于 kk。

请你求出最少需要修改多少个元素。

*\text{*} 本题中,数列的 mex⁡\operatorname{mex} 被定义为数列中最小未出现的自然数,例如:

  • mex⁡{1,2,3}=0\operatorname{mex}\{1,2,3\}=0,因为 00 是自然数。
  • mex⁡{0,1,3}=2\operatorname{mex}\{0,1,3\}=2。
  • mex⁡{0,1,2}=3\operatorname{mex}\{0,1,2\}=3。

输入格式

第一行两个整数 n,kn,k,表示数列长度和小 R 讨厌的数。

第二行 nn 个整数,第 ii 个整数为 aia_i,表示这个数列的第 ii 项。

输出格式

一行一个整数,表示最少需要修改的元素个数。

样例

5 2
1 0 1 3 0
2

题目来源:洛谷 P9199