Virus

题意翻译

有 $n$ 个房子在环上排列。对所有 $1\le i\le n-1$，第 $i$ 个房子与第 $i+1$ 个房子相邻；特别地，第 $n$ 个房子与第 $1$ 个房子也相邻。 一开始，这 $n$ 个房子中有 $m$ 个房子被病毒感染了。在之后的每天早上，Cirno 可以选择一个未被感染的房子并对其进行保护，被保护过的房子不会被病毒感染。 在每一天，事件发生的顺序如下： - Cirno 选择一个未被感染的房子并对其进行保护，阻止病毒的传播。 - 对所有未被感染病毒的房子，若其与至少一个被感染的房子相邻，则该房子会被染上病毒。 Cirno 想要阻止病毒的传播，若他采用最优策略去保护房子，请求出最终被感染房子数的最小值。 注意：在每一天，Cirno 总是在病毒开始传播前进行保护操作。一个被保护过的房子不会被再次感染。

题目描述

There are $ n $ houses numbered from $ 1 $ to $ n $ on a circle. For each $ 1 \leq i \leq n - 1 $ , house $ i $ and house $ i + 1 $ are neighbours; additionally, house $ n $ and house $ 1 $ are also neighbours. Initially, $ m $ of these $ n $ houses are infected by a deadly virus. Each morning, Cirno can choose a house which is uninfected and protect the house from being infected permanently. Every day, the following things happen in order: - Cirno chooses an uninfected house, and protect it permanently. - All uninfected, unprotected houses which have at least one infected neighbor become infected. Cirno wants to stop the virus from spreading. Find the minimum number of houses that will be infected in the end, if she optimally choose the houses to protect. Note that every day Cirno always chooses a house to protect before the virus spreads. Also, a protected house will not be infected forever.

输入输出格式

输入格式

The input consists of multiple test cases. The first line contains a single integer $ t $ ( $ 1 \leq t \leq 10^4 $ ) — the number of test cases. Description of test cases follows. The first line of each test case consists of two positive integers $ n, m $ ( $ 5 \leq n \leq 10^9 $ , $ 1 \leq m \leq \min(n, 10^5) $ ) — the number of houses on the circle, and the number of houses that are initially infected. The second line of each test case consists of $ m $ distinct positive integers $ a_1, a_2, \cdots , a_m $ ( $ 1 \leq a_i \leq n $ ) — the indices of the houses infected initially. It is guaranteed that the sum of $ m $ over all test cases does not exceed $ 10^5 $ .

输出格式

For each test case, output an integer on a separate line, which is the minimum number of infected houses in the end.

输入输出样例

输入样例 #1

8
10 3
3 6 8
6 2
2 5
20 3
3 7 12
41 5
1 11 21 31 41
10 5
2 4 6 8 10
5 5
3 2 5 4 1
1000000000 1
1
1000000000 4
1 1000000000 10 16

输出样例 #1

7
5
11
28
9
5
2
15

说明

In the first test case: At the start of the first day, house $ 3 $ , $ 6 $ , $ 8 $ are infected. Choose house $ 2 $ to protect. At the start of the second day, house $ 3 $ , $ 4 $ , $ 5 $ , $ 6 $ , $ 7 $ , $ 8 $ , $ 9 $ are infected. Choose house $ 10 $ to protect. At the start of the third day, no more houses are infected. In the second test case: At the start of the first day, house $ 2 $ , $ 5 $ are infected. Choose house $ 1 $ to protect. At the start of the second day, house $ 2 $ , $ 3 $ , $ 4 $ , $ 5 $ , $ 6 $ are infected. No more available houses can be protected.

**题目大意：**

在一条环线上有 $ 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 $。

**输出格式：**

对于每个测试案例，输出一个整数，表示最终被感染房子的最小数量。

**输入输出样例：**

**输入样例 #1:**

```
8
10 3
3 6 8
6 2
2 5
20 3
3 7 12
41 5
1 11 21 31 41
10 5
2 4 6 8 10
5 5
3 2 5 4 1
1000000000 1
1
1000000000 4
1 1000000000 10 16
```

**输出样例 #1:**

```
7
5
11
28
9
5
2
15
```

**说明：**

在第一个测试案例中：

- 第一天开始时，房子 $ 3 $，$ 6 $，$ 8 $ 被感染。选择保护房子 $ 2 $。
- 第二天开始时，房子 $ 3 $，$ 4 $，$ 5 $，$ 6 $，$ 7 $，$ 8 $，$ 9 $ 被感染。选择保护房子 $ 10 $。
- 第三天开始时，没有更多的房子被感染。

在第二个测试案例中：

- 第一天开始时，房子 $ 2 $，$ 5 $ 被感染。选择保护房子 $ 1 $。
- 第二天开始时，房子 $ 2 $，$ 3 $，$ 4 $，$ 5 $，$ 6 $ 被感染。没有更多的房子可以被保护。**题目大意：** 在一条环线上有 $ 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 $。 **输出格式：** 对于每个测试案例，输出一个整数，表示最终被感染房子的最小数量。 **输入输出样例：** **输入样例 #1:** ``` 8 10 3 3 6 8 6 2 2 5 20 3 3 7 12 41 5 1 11 21 31 41 10 5 2 4 6 8 10 5 5 3 2 5 4 1 1000000000 1 1 1000000000 4 1 1000000000 10 16 ``` **输出样例 #1:** ``` 7 5 11 28 9 5 2 15 ``` **说明：** 在第一个测试案例中： - 第一天开始时，房子 $ 3 $，$ 6 $，$ 8 $ 被感染。选择保护房子 $ 2 $。 - 第二天开始时，房子 $ 3 $，$ 4 $，$ 5 $，$ 6 $，$ 7 $，$ 8 $，$ 9 $ 被感染。选择保护房子 $ 10 $。 - 第三天开始时，没有更多的房子被感染。 在第二个测试案例中： - 第一天开始时，房子 $ 2 $，$ 5 $ 被感染。选择保护房子 $ 1 $。 - 第二天开始时，房子 $ 2 $，$ 3 $，$ 4 $，$ 5 $，$ 6 $ 被感染。没有更多的房子可以被保护。