← 返回题目列表

Codeforces · 2025/C

C. 新游戏

中文机器翻译题面 查看原题

Monocarp 想玩一款新游戏。游戏使用一副 $$$n$$$ 卡,其中第 $$$i$$$ 卡上正好写有一个整数 $$$a_i$$$。

在游戏开始时的第一个回合,Monocarp 可以从牌组中拿取任何卡牌。在随后的每个回合中,Monocarp 只能拿走一张与上一回合所拿的卡片上的数字相同或比上一回合所拿的卡片上的数字大 1 的卡片。

换句话说,如果Monocarp在上一回合拿了一张编号为$$$x$$$的牌,那么在当前回合他可以拿一张编号为$$$x$$$的牌或一张编号为$$$x + 1$$$的牌。 Monocarp 可以拿走任何符合该条件的牌,无论其在牌组中的位置如何。

Monocarp 在当前回合拿走一张牌后,它将从牌库中移除。

根据游戏规则,Monocarp拿走的卡片上写的不同数字的数量不得超过$$$k$$$。

如果在一个回合后,Monocarp 无法在不违反所描述规则的情况下拿走一张牌,则游戏结束。

你的任务是确定 Monocarp 在游戏过程中可以从牌组中拿走的牌的最大数量,前提是他在第一回合可以从牌组中拿走任何牌。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le k \le n \le 200\,000$$$) - 一副牌中的牌数以及 Monocarp 所采用的牌上可以写入的不同数字的最大数量。

第二行包含整数序列 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^{9}$$$),其中 $$$a_i$$$ 是写在第 $$$i$$$ 卡上的数字。

输入的附加约束:所有测试用例的 $$$n$$$ 总和不超过 $$$200\,000$$$。

输出

对于每个测试用例,打印 Monocarp 在游戏过程中可以从牌组中拿走的最大牌数,假设在第一回合他可以从牌组中拿走任何牌。

示例

输入 #1

4
10 2
5 2 4 3 4 3 4 5 3 2
5 1
10 11 10 11 10
9 3
4 5 4 4 6 5 4 4 6
3 2
1 3 1

输出 #1

6
3
9
2

注意

在第一个示例中,Monocarp 需要拿走任何一张编号为 $$$3$$$ 的牌。在接下来的两个回合中,他需要拿走剩下的两张数字为 $$$3$$$ 的牌。在接下来的三个回合中,他需要拿三张数字为 $$$4$$$ 的牌。之后,Monocarp 将无法再从牌堆中拿走任何牌,他将拥有 $$$6$$$ 卡。