Water The Garden
机翻
现在是冬天，Max 决定是时候给花园浇水了。
花园可以表示为 n 个连续的花坛，从 1 到 n 编号。 k 个花坛包含水龙头（第 i 个龙头位于花坛 xi 中），如果打开，就开始向相邻的花坛供水。 如果打开位于花坛 xi 的水龙头，则经过一秒钟，花坛 xi 将被浇水; 经过两秒钟，从区间 [xi - 1, xi + 1] 的花坛将被浇水（如果它们存在）; 经过 j 秒钟 （ j 是整数)，花坛从区间 [xi - ( j - 1), xi + ( j - 1)] 将被浇水（如果它们存在）。 在几秒钟内不会发生任何变化，例如，我们不能说在经过 2.5 秒后区间 [xi - 2.5, xi + 2.5] 将会被浇水; 在那一刻只有区间 [xi - 2, xi + 2] 将被浇水。
测试 1 的花园。白色表示没有水龙头的花坛，红色表示有水龙头的花坛。
打开龙头后经过 2 秒的测试 1 的花园。 白色表示未浇水的花坛，蓝色表示浇过水的花坛。
Max 想要同时打开所有水龙头，现在他想知道，他打开一些水龙头后到整个花园被浇水所需的最少秒数。帮他找到答案！
输入
第一行包含一个整数 t —— 要解决的测试用例数 (1 ≤ t ≤ 200)。
然后是t个测试用例。每个测试用例的第一行包含两个整数 n 和 k (1 ≤ n ≤ 200，1 ≤ k ≤ n) —— 花坛数量和水龙头数量。
下一行包含 k 个整数 xi (1 ≤ xi ≤ n) ——第 i 个龙头的位置。 保证每个 
条件都满足 xi - 1 < xi 。
保证所有测试用例中 n 的总和不超过 200 。
请注意，在黑客中，您必须设置 t = 1。
输出
请为每个测试用例打印一个整数——打开一些水龙头后 Max 需要转过的最少秒数，直到整个花园浇水。
注意
第一个例子包含3个测试：
- 有5个花园床，在床3上有一个水龙头。如果我们打开水龙头，然后过1秒后，只有床3会被灌溉；过2秒后，床[1, 3]会被灌溉；过3秒后，所有床都会被灌溉。
- 有3个花园床，每个床上都有一个水龙头。如果我们打开它们所有的水龙头，在1秒后，所有的床都会被灌溉。
- 有4个花园床，只有一个水龙头在床1。例如，浇灌床4需要4秒钟。
Description
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 xi), which, if turned on, start delivering water to neighbouring beds. If the tap on the bed xi is turned on, then after one second has passed, the bed xi will be watered; after two seconds have passed, the beds from the segment [xi - 1, xi + 1] will be watered (if they exist); after j seconds have passed (j is an integer number), the beds from the segment [xi - ( j - 1), xi + ( j - 1)] will be watered (if they exist). Nothing changes during the seconds, so, for example, we can't say that the segment [xi - 2.5, xi + 2.5] will be watered after 2.5 seconds have passed; only the segment [xi - 2, xi + 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!
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 xi (1 ≤ xi ≤ n) — the location of i-th water tap. It is guaranteed that for each condition xi - 1 < xi 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.
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.
Input
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 xi (1 ≤ xi ≤ n) — the location of i-th water tap. It is guaranteed that for each condition xi - 1 < xi 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.
Output
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.
Samples
3
5 1
3
3 3
1 2 3
4 1
1
3
1
4
Note
The first example consists of 3 tests:
- 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.
- 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.
- There are 4 garden beds, and only one tap in the bed 1. It will take 4 seconds to water, for example, bed 4.
相关
在以下作业中: