题目描述

WhiteRaptor 终于在 TheRaptorLand 找到了他的同类！与普通的 WhiteRaptor 不同，TheRaptorLand 拥有各种颜色的迅猛龙：PinkRaptor、BlueRaptor 和 GreenRaptor。

WhiteRaptor 将 TheRaptorLand 中的所有 $n$ 只迅猛龙排成一行，从左到右编号为 $1$ 到 $n$。从左数第 $i$ 只迅猛龙的颜色为 $c[i]$。他想选择一些迅猛龙永远陪伴在他的地下室。然而，他只能通过从队伍的左端和右端移除零只或多只迅猛龙，并保留所有剩余的迅猛龙来实现这一点。

为了确保没有剩余的迅猛龙被排斥，他希望最常见迅猛龙颜色的频率与最不常见迅猛龙颜色的频率之间的差值不超过 $k$。注意，如果没有某种颜色的迅猛龙剩余，则最不常见颜色的频率将为 $0$。

请帮助 WhiteRaptor 找出他能保留的迅猛龙的最大数量！

输入格式

你的程序需要从标准输入读取数据。

输入的第一行包含两个整数 $n$ 和 $k$。

输入的第二行包含 $n$ 个由空格分隔的整数 $c[1], c[2], \dots, c[n]$。

输出格式

你的程序需要向标准输出写入数据。

输出一个整数，表示他能保留的迅猛龙的最大数量。

11 2
2 2 1 2 1 3 2 1 2 1 1

7

6 2
2 1 3 3 3 3

5

7 0
1 2 1 2 1 2 1

0

提示

样例测试 #1 解释

从迅猛龙 $3$ 到迅猛龙 $9$，$c[i] = 1, 2, 3$ 的迅猛龙数量分别为 $3, 3, 1$。由于最大频率与最小频率之间的差值不超过 $k = 2$，这组迅猛龙满足 WhiteRaptor 的标准。

一个无效的迅猛龙集合的例子是从迅猛龙 $3$ 到迅猛龙 $10$，因为增加另一只 $c[i] = 1$ 的迅猛龙会导致最常见颜色的频率变为 $4$。由此产生的最大频率与最小频率之间的差值为 $3$，超过了 $k = 2$。

可以证明，$7$ 是 WhiteRaptor 在仍满足其标准的情况下能保留的迅猛龙的最大数量。

样例测试 #2 解释

WhiteRaptor 应该选择从迅猛龙 $1$ 到迅猛龙 $5$ 的迅猛龙。

样例测试 #3 解释

由于任何连续的迅猛龙序列都不会包含 $c[i] = 3$ 的迅猛龙，最不常见颜色的频率将始终为 $0$。这意味着 WhiteRaptor 无法选择任何非空的迅猛龙序列。因此，输出为 $0$。

注意，这个测试用例满足子任务 5 的条件，因为我们可以令 $j = n$（没有颜色 3 的迅猛龙会出现）。

子任务

对于所有测试用例，输入数据满足以下限制：

• $1 \leq n \leq 200\,000$
• $0 \leq k \leq 200\,000$
• 对于所有 $1 \leq i \leq n$，有 $1 \leq c[i] \leq 3$

你的程序将在满足以下限制的输入实例上进行测试：

翻译由 DeepSeek V3.2 完成