题目翻译

配点 : $400$ 点

问题描述

拉斯克有一个长度为 $N$ 的数列 $a$。

数列的无聊度，指的是连续子序列中由相同元素组成的最长子序列的长度。

拉斯克想通过将数列 $a$ 的元素替换为最多 $K$ 个整数，使得无聊度尽可能小。

请计算能够达到的最小无聊度。

约束条件

• 输入为整数。
• $1 \\leq K \\leq N \\leq 2\\times 10^5$
• $1 \\leq a_i \\leq N$

---

输入

输入以以下格式从标准输入中给出。

$N$ $K$ $a_1$ $a_2$ $\\ldots$ $a_N$

输出

输出在将数列 $a$ 的元素替换为最多 $K$ 个整数的情况下，能够达到的最小无聊度。

---

示例 1

10 2
3 3 3 3 4 4 4 4 4 4

输出示例 1

3

将左起第一个元素替换为 $1$，将第七个元素替换为 $2$，则数列变为

$1, 3, 3, 3, 4, 4, 2, 4, 4, 4$

此时的无聊度为 $3$。

---

示例 2

9 2
3 3 4 4 4 4 4 4 4

输出示例 2

2

将左起第四个元素替换为 $5$，将第七个元素替换为 $1$，则数列变为

$3, 3, 4, 5, 4, 4, 1, 4, 4$

此时的无聊度为 $2$。

---

示例 3

5 5
3 1 4 1 5

输出示例 3

1

可以不进行任何替换。

---