Standard Free2play

**题目描述** 您现在正在玩一个游戏，您初始在一个高度 $h$ 的悬崖 悬崖沿壁高度为 $1-h$ 的这些位置均有平台，平台有两种状态，被选中/不被选中，您可以认为只有被选中的平台才出现在这个悬崖上且你可以站在上面。 初始时有 $n$ 个平台为被选中，保证平台 $h$ 被选中，您每次可以进行一个操作，不妨假设您当前站在平台 $x$ 处（此时平台 $x$ 一定被选中），即让平台 $x$ 变成未被选中，而平台 $x - 1$ 变成相反的状态。 您非常的脆弱，所以不能跌落超过$2$的高度，比如您可以从高度为$3$的平台跌落到高度为$1$的平台，但不能从高度为$3$的平台跌落到地面$($高度：$0)$ 现在您想要回到地面，即高度为$0$ 您可以使用一种魔力水晶，即其可以将任意一个平台修改成指定的状态。 现在希望您求出回到地面最少需要使用多少颗魔力水晶？ **输入格式** 第一行一个正整数$q(1\le q\le100)$表示$q$组询问 接下来$q$组询问，每组询问格式如下： 第一行两个正整数分别表示 $h(1\le h\le10^9)$ 和$n(1\le n\le \min(h,2*10^5))$ 接下来一行$n$个正整数依次表示初始被选中的平台的高度$p_1,p_2...p_n(h=p_1>p_2>...>p_n>0)$ 保证$\sum n \le 2*10^5$ **输出格式** 对于每个询问，输出最少需要使用的魔力水晶数量。 翻译：$\rm Mital$

You are playing a game where your character should overcome different obstacles. The current problem is to come down from a cliff. The cliff has height $ h $ , and there is a moving platform on each height $ x $ from $ 1 $ to $ h $ . Each platform is either hidden inside the cliff or moved out. At first, there are $ n $ moved out platforms on heights $ p_1, p_2, \dots, p_n $ . The platform on height $ h $ is moved out (and the character is initially standing there). If you character is standing on some moved out platform on height $ x $ , then he can pull a special lever, which switches the state of two platforms: on height $ x $ and $ x - 1 $ . In other words, the platform you are currently standing on will hide in the cliff and the platform one unit below will change it state: it will hide if it was moved out or move out if it was hidden. In the second case, you will safely land on it. Note that this is the only way to move from one platform to another. Your character is quite fragile, so it can safely fall from the height no more than $ 2 $ . In other words falling from the platform $ x $ to platform $ x - 2 $ is okay, but falling from $ x $ to $ x - 3 $ (or lower) is certain death. Sometimes it's not possible to come down from the cliff, but you can always buy (for donate currency) several magic crystals. Each magic crystal can be used to change the state of any single platform (except platform on height $ h $ , which is unaffected by the crystals). After being used, the crystal disappears. What is the minimum number of magic crystal you need to buy to safely land on the $ 0 $ ground level?

The first line contains one integer $ q $ ( $ 1 \le q \le 100 $ ) — the number of queries. Each query contains two lines and is independent of all other queries. The first line of each query contains two integers $ h $ and $ n $ ( $ 1 \le h \le 10^9 $ , $ 1 \le n \le \min(h, 2 \cdot 10^5) $ ) — the height of the cliff and the number of moved out platforms. The second line contains $ n $ integers $ p_1, p_2, \dots, p_n $ ( $ h = p_1 > p_2 > \dots > p_n \ge 1 $ ) — the corresponding moved out platforms in the descending order of their heights. The sum of $ n $ over all queries does not exceed $ 2 \cdot 10^5 $ .

For each query print one integer — the minimum number of magic crystals you have to spend to safely come down on the ground level (with height $ 0 $ ).

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

0
1
2
0