← 返回题目列表

Codeforces · 1238/C

C. 标准 Free2play

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

您正在玩一款游戏,您的角色应该克服不同的障碍。当前的问题是如何从悬崖上下来。悬崖的高度为$$$h$$$,从$$$1$$$到$$$h$$$的每个高度$$$x$$$上都有一个移动平台。

每个平台要么隐藏在悬崖内,要么移出。首先,有 $$$n$$$ 移出高度为 $$$p_1、p_2、\dots、p_n$$$ 的平台。高度 $$$h$$$ 的平台被移出(角色最初站在那里)。

如果你的角色站在高度 $$$x$$$ 的某个移出的平台上,那么他可以拉动一个特殊的杠杆,这会切换两个平台的状态:高度 $$$x$$$ 和 $$$x - 1$$$。换句话说,你当前所站的平台会隐藏在悬崖中,而下方一个单位的平台会改变其状态:移出则隐藏,隐藏则移出。在第二种情况下,您将安全着陆。请注意,这是从一个平台转移到另一个平台的唯一方法。

你的角色非常脆弱,所以它可以安全地从不超过$$$2$$$的高度坠落。换句话说,从 $$$x$$$ 平台跌落到 $$$x - 2$$$ 平台是可以的,但从 $$$x$$$ 跌落到 $$$x - 3$$$ (或更低)则必死无疑。

有时不可能从悬崖上下来,但你总是可以购买(捐赠货币)一些魔法水晶。每个魔法水晶都可以用来改变任何单个平台的状态(高度 $$$h$$$ 的平台除外,它不受水晶的影响)。使用后,水晶就会消失。

安全降落在$$$0$$$地面上至少需要购买多少魔水晶?

输入

第一行包含一个整数 $$$q$$$ ($$$1 \le q \le 100$$$) — 查询数。每个查询包含两行并且独立于所有其他查询。

每个查询的第一行包含两个整数 $$$h$$$ 和 $$$n$$$ ($$$1 \le h \le 10^9$$$, $$$1 \le n \le \min(h, 2 \cdot 10^5)$$$) — 悬崖的高度和移出平台的数量。

第二行包含 $$$n$$$ 整数 $$$p_1, p_2, \dots, p_n$$$ ($$$h = p_1 > p_2 > \dots > p_n \ge 1$$$) — 相应的移出平台按高度降序排列。

所有查询的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个查询,打印一个整数——安全降落到地面(高度 $$$0$$$)所需的最少魔法水晶数量。

示例

输入 #1

4
3 2
3 1
8 6
8 7 6 5 3 2
9 6
9 8 5 4 3 1
1 1
1

输出 #1

0
1
2
0