CF1704C Virus

有 $n$ 间房屋，编号从 $1$ 到 $n$，它们围成一个环。对于每个 $1 \leq i \leq n-1$，第 $i$ 间房屋和第 $i+1$ 间房屋是相邻的；此外，第 $n$ 间房屋和第 $1$ 间房屋也是相邻的。 最初，这 $n$ 间房屋中有 $m$ 间被致命病毒感染。每天早晨，Cirno 可以选择一间未被感染的房屋，并永久性地保护这间房屋，使其永远不会被感染。 每天会按如下顺序发生事件： - Cirno 选择一间未被感染的房屋，并将其永久保护。 - 所有未被感染且未被保护的房屋，如果至少有一个相邻房屋被感染，则会被感染。 Cirno 想要阻止病毒的传播。如果她每次都最优地选择要保护的房屋，求最终最少会有多少间房屋被感染。 注意，每天 Cirno 总是在病毒传播前选择要保护的房屋。同时，被保护的房屋永远不会被感染。

输入包含多组测试数据。第一行包含一个整数 $t$（$1 \leq t \leq 10^4$），表示测试用例的数量。接下来是每组测试用例的描述。 每组测试用例的第一行包含两个正整数 $n, m$（$5 \leq n \leq 10^9$，$1 \leq m \leq \min(n, 10^5)$），分别表示环上的房屋数量和最初被感染的房屋数量。 每组测试用例的第二行包含 $m$ 个互不相同的正整数 $a_1, a_2, \cdots, a_m$（$1 \leq a_i \leq n$），表示最初被感染的房屋编号。 保证所有测试用例中 $m$ 的总和不超过 $10^5$。

对于每组测试用例，输出一个整数，表示最终最少会有多少间房屋被感染。每个答案占一行。

在第一个测试用例中： 第一天开始时，房屋 $3$、$6$、$8$ 被感染。选择房屋 $2$ 进行保护。 第二天开始时，房屋 $3$、$4$、$5$、$6$、$7$、$8$、$9$ 被感染。选择房屋 $10$ 进行保护。 第三天开始时，不会再有房屋被感染。 在第二个测试用例中： 第一天开始时，房屋 $2$、$5$ 被感染。选择房屋 $1$ 进行保护。 第二天开始时，房屋 $2$、$3$、$4$、$5$、$6$ 被感染。没有更多可保护的房屋。 由 ChatGPT 4.1 翻译