← 返回题目列表

Codeforces · 1593/C

C. 拯救更多老鼠

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

坐标线上有一只猫、$$$k$$$ 老鼠和一个洞。猫位于点$$$0$$$,洞位于点$$$n$$$。所有老鼠都位于猫和洞之间:第 $$$i$$$ 只老鼠位于点 $$$x_i$$$ ($$$0 < x_i < n$$$)。在每个点上,可以定位许多小鼠。

一秒钟内,发生以下情况。首先,恰好有一只鼠标向右移动 $$$1$$$。如果老鼠到达洞里,它就会隐藏起来(即老鼠不会再移动到任何点,也不会被猫吃掉)。然后(老鼠完成移动后)猫向右移动$$$1$$$。如果在新猫的位置上有一些老鼠,猫就会吃掉它们(之后它们将无法移动)。执行这些操作直到没有任何老鼠被隐藏或没有被吃掉。

换句话说,第一次移动是由鼠标完成的。如果鼠标到达了洞,它就被保存了。然后猫采取了行动。猫会吃掉位于其到达点处的老鼠(如果猫到达了洞口,则不会吃任何人)。

每秒,您都可以选择要移动的鼠标。最多有多少只老鼠可以到达洞而不被吃掉?

输入

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

每个测试用例由两行组成。第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$2 \le n \le 10^9$$$, $$$1 \le k \le 4 \cdot 10^5$$$)。第二行包含 $$$k$$$ 整数 $$$x_1, x_2, \dots x_k$$$ ($$$1 \le x_i < n$$$) — 小鼠的初始坐标。

保证输入中给出的所有 $$$k$$$ 的总和不超过 $$$4 \cdot 10^5$$$。

输出

对于每个测试用例,在单独的行上输出一个整数 $$$m$$$ ($$$m \ge 0$$$) — 可以到达洞而不被吃掉的老鼠的最大数量。

示例

输入 #1

3
10 6
8 7 5 4 9 4
2 8
1 1 1 1 1 1 1 1
12 11
1 2 3 4 5 6 7 8 9 10 11

输出 #1

3
1
4