P16728 [GKS 2019 #B] Diverse Subarray

Vanity 的架子上有 $N$ 个小饰品，从左到右编号为 $1, 2, \dots, N$。饰品有不同的类型，用正整数表示。架子上第 $i$ 个饰品的类型为 $A_i$。 今天她要出国看望家人，想尽量多带一些饰品。但由于时间紧迫，Vanity 只能拿走连续的一段区间。形式化地说，Vanity 选择两个下标 $l$ 和 $r$，取走编号为 $l, l+1, \dots, r-1, r$ 的所有饰品。此外，根据税务规定，如果 Vanity 在所选区间内某种类型的饰品数量超过 $S$，机场安检就会将该类型的**所有**饰品都扔掉。 例如，假设 $S = 2$，Vanity 带了六个饰品：一个类型 $0$，两个类型 $1$，三个类型 $2$。她可以保留类型 $0$ 的饰品和两个类型 $1$ 的饰品，但类型 $2$ 的所有饰品都会被扔掉！ Vanity 需要选择 $l$ 和 $r$，使得她能带给家人的饰品数量最多。她最多能带多少个饰品？

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。每个测试用例的第一行包含两个整数 $N$ 和 $S$，分别表示饰品的数量以及允许的某种类型的最大饰品数量。第二行包含 $N$ 个整数，其中第 $i$ 个整数表示第 $i$ 个饰品的类型 $A_i$。

对于每个测试用例，输出一行，格式为 `Case #x: y`，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是 Vanity 能带给家人的最大饰品数量。

在样例 #2 中，Vanity 应选择 $l = 1$ 和 $r = 8$。这样她可以将全部 $8$ 个饰品带到机场。由于她拥有超过 $S = 1$ 个类型 $500$ 的饰品，这些类型 $500$ 的饰品会被扔掉，所以她总共能带给家人 $6$ 个饰品。 在样例 #3 中，Vanity 应选择 $l = 1$ 和 $r = 9$。这样她可以带 $9$ 个饰品到机场，类型分别为 $100$、$200$、$8$、$8$、$8$、$8$、$8$、$300$ 和 $400$。由于她拥有超过 $S = 1$ 个类型 $8$ 的饰品，这些类型 $8$ 的饰品会被扔掉，所以她总共能带给家人 $4$ 个饰品。 在样例 #4 中，Vanity 应选择 $l = 1$ 和 $r = 12$。这样她可以将全部 $12$ 个饰品带到机场。由于她拥有超过 $S = 2$ 个类型 $1$ 和类型 $2$ 的饰品，这些类型 $1$ 和类型 $2$ 的饰品会被扔掉，所以她总共能带给家人 $6$ 个饰品。 **注意**：对于本题，我们不建议使用解释型/较慢的语言。 ### 限制条件 $1 \le T \le 100$。 $1 \le A_i \le 10^5$。 $1 \le S \le N$。 **测试集 1（可见）** $1 \le N \le 1000$。 **测试集 2（隐藏）** $1 \le N \le 10^5$。 翻译由 DeepSeek V4 Pro 完成