Virus
Contest: CodeTON Round 2 (Div. 1 + Div. 2, Rated, Prizes!)
Difficulty rating: 1200
Tags: greedy, implementation, sortings

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.

Input format:
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$$$.

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

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
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.

Example input:
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

Example output:
7
5
11
28
9
5
2
15

Editorial:
First, considering it is easier to calculate the number of houses which are not infected, so we focus on it firstly.
Conspicuously, if between $$$a_i$$$ and $$$a_{i+1}$$$ there are $$$x$$$ houses (Array $$$a$$$ has been sorted.), and the infection will last $$$y$$$ days, there will remain $$$x-2 \times y$$$ houses on the end. Simultaneously, every day we can protect at least one house permanently, which indicates that for every distance between $$$a_i$$$ and $$$a_{i+1}$$$, if $$$x- 2\times y > 0$$$, we have an opportunity to get one house protected.
Moreover, the longer uninfected segments have priorities, because we can set two houses to stop the spread of inflection and the loss per day will be prevented. By contrast, for shorter segments, when all the houses in this segment are infected, then there won't be any loss afterwards. In other words, the loss of longer segments will last for longer time if we do not take actions in time. As a result, if we operate the longer segments as early as possible, we can protect more houses.
In conclusion, our final strategy can be decribed as following: Sort the uninfected segments of houses according to their length, then the longer the segment is, the earlier we will deal with the houses lying on the side of the segment.