CF920A.Water The Garden

It is winter now, and Max decided it's about time he watered the garden.

The garden can be represented as n consecutive garden beds, numbered from 1 to n. k beds contain water taps (i-th tap is located in the bed x__i), which, if turned on, start delivering water to neighbouring beds. If the tap on the bed x__i is turned on, then after one second has passed, the bed x__i will be watered; after two seconds have passed, the beds from the segment [x__i - 1, x__i + 1] will be watered (if they exist); after j seconds have passed (j is an integer number), the beds from the segment [x__i - (j - 1), x__i + (j - 1)] will be watered (if they exist). Nothing changes during the seconds, so, for example, we can't say that the segment [x__i - 2.5, x__i + 2.5] will be watered after 2.5 seconds have passed; only the segment [x__i - 2, x__i + 2] will be watered at that moment.

The garden from test 1. White colour denotes a garden bed without a tap, red colour — a garden bed with a tap.

The garden from test 1 after 2 seconds have passed after turning on the tap. White colour denotes an unwatered garden bed, blue colour — a watered bed.

Max wants to turn on all the water taps at the same moment, and now he wonders, what is the minimum number of seconds that have to pass after he turns on some taps until the whole garden is watered. Help him to find the answer!

现在正值冬季，Max 觉得是时候给花园浇水了。

花园可以表示为 $n$ 个连续的花坛，编号从 $1$ 到 $n$。其中有 $k$ 个花坛装有水龙头（第 $i$ 个水龙头位于花坛 $x_i$），一旦打开，便会向相邻花坛供水。若位于花坛 $x_i$ 的水龙头被打开，则：

• 经过 $1$ 秒后，花坛 $x_i$ 将被浇灌；
• 经过 $2$ 秒后，区间 $[x_i - 1,\, x_i + 1]$ 内的所有花坛将被浇灌（若该区间内存在对应花坛）；
• 经过 $j$ 秒后（$j$ 为整数），区间 $[x_i - (j - 1),\, x_i + (j - 1)]$ 内的所有花坛将被浇灌（若该区间内存在对应花坛）。

秒级时间点之间不发生任何变化，因此例如我们不能说经过 $2.5$ 秒后区间 $[x_i - 2.5,\, x_i + 2.5]$ 被浇灌；在该时刻，仅有区间 $[x_i - 2,\, x_i + 2]$ 被浇灌。

测试用例 1 中的花园。白色表示无水龙头的花坛，红色表示装有水龙头的花坛。

测试用例 1 中，在打开水龙头并经过 $2$ 秒后的花园状态。白色表示未被浇灌的花坛，蓝色表示已被浇灌的花坛。

Max 计划在同一时刻打开所有水龙头，他现在想知道：从打开部分（或全部）水龙头起，至少需要经过多少秒，才能使整个花园都被浇灌？请帮助他求出答案！

The first line contains one integer t — the number of test cases to solve (1 ≤ t ≤ 200).

Then t test cases follow. The first line of each test case contains two integers n and k (1 ≤ n ≤ 200, 1 ≤ k ≤ n) — the number of garden beds and water taps, respectively.

Next line contains k integers x__i (1 ≤ x__i ≤ n) — the location of i-th water tap. It is guaranteed that for each condition x__i - 1 < x__i holds.

It is guaranteed that the sum of n over all test cases doesn't exceed 200.

Note that in hacks you have to set t = 1.

第一行包含一个整数 $t$ —— 需要解决的测试用例数量（$1 \leq t \leq 200$）。

接下来是 $t$ 个测试用例。每个测试用例的第一行包含两个整数 $n$ 和 $k$（$1 \leq n \leq 200$，$1 \leq k \leq n$）—— 分别表示花园床的数量和水龙头的数量。

下一行包含 $k$ 个整数 $x_i$（$1 \leq x_i \leq n$）—— 表示第 $i$ 个水龙头的位置。保证对每个 ，均满足条件 $x_{i-1} < x_i$。

保证所有测试用例中 $n$ 的总和不超过 $200$。

注意：在 hack 中，你必须设置 $t = 1$。

For each test case print one integer — the minimum number of seconds that have to pass after Max turns on some of the water taps, until the whole garden is watered.

对于每个测试用例，输出一个整数——即 Max 打开部分水龙头后，整个花园被完全浇灌所需的最少秒数。

The first example consists of 3 tests:

1. There are 5 garden beds, and a water tap in the bed 3. If we turn it on, then after 1 second passes, only bed 3 will be watered; after 2 seconds pass, beds [1, 3] will be watered, and after 3 seconds pass, everything will be watered.
2. There are 3 garden beds, and there is a water tap in each one. If we turn all of them on, then everything will be watered after 1 second passes.
3. There are 4 garden beds, and only one tap in the bed 1. It will take 4 seconds to water, for example, bed 4.

第一个示例包含 3 个测试用例：

1. 共有 5 个花坛，水龙头位于第 3 个花坛。若将其打开，则 1 秒后仅第 3 个花坛被浇灌；2 秒后，第 [1, 3] 个花坛被浇灌；3 秒后，所有花坛均被浇灌。
2. 共有 3 个花坛，每个花坛均有一个水龙头。若将所有水龙头同时打开，则 1 秒后所有花坛均被浇灌。
3. 共有 4 个花坛，仅在第 1 个花坛处有一个水龙头。例如，浇灌第 4 个花坛需要 4 秒。