P15849 [NOISG 2026 Finals] 三只迅猛龙 / 3 Raptors【暂无数据】

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]$。

你的程序需要向标准输出写入数据。 输出一个整数，表示他能保留的迅猛龙的最大数量。

### 样例测试 #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$ 你的程序将在满足以下限制的输入实例上进行测试： | 子任务 | 分数 | 额外约束条件 | |:-:|:-:|:-:| | 0 | 0 | 样例测试用例 | | 1 | 5 | $n \leq 500$ | | 2 | 9 | $n \leq 2000$ | | 3 | 11 | $c[i] \leq 2$ | | 4 | 15 | $k = 0$ | | 5 | 16 | 存在一个 $1 \leq j \leq n$，使得对于所有 $i \leq j$ 有 $c[i] \ne 3$，且对于所有 $i > j$ 有 $c[i] = 3$ | | 6 | 20 | 在任何连续的 3 只或更多迅猛龙的序列中，颜色 3 是最不常见的。 | | 7 | 24 | 无额外约束 | 翻译由 DeepSeek V3.2 完成