← 返回题目列表

Codeforces · 920/A

A. 给花园浇水

中文机器翻译题面 查看原题

现在是冬天,麦克斯决定是时候给花园浇水了。

花园可以表示为 n 个连续的花园床,编号从 1 到 n。 k 个床位包含水龙头(第 i 个水龙头位于床位 xi 中),如果打开,则开始向相邻床位供水。如果床xi上的水龙头打开,那么一秒过去后,床xi就会被浇水;两秒过去后,段 [xi - 1, xi + 1] 中的床将被浇水(如果存在); j 秒过去后(j 是整数),段 [xi - (j - 1), xi + (j - 1)] 中的床将被浇水(如果存在)。在几秒钟内没有任何变化,因此,例如,我们不能说段 [xi - 2.5, xi + 2.5] 将在 2.5 秒过去后被浇水;此时只有 [xi - 2, xi + 2] 段会被浇水。

测试 1 中的花园。白色表示没有水龙头的花园床,红色表示有水龙头的花园床。

打开水龙头 2 秒后测试 1 中的花园。白色表示未浇水的花园床,蓝色表示浇过水的花园床。

Max想同时打开所有水龙头,现在他想知道,在他打开一些水龙头后,至少要经过多少秒才能给整个花园浇水。帮助他找到答案!

输入

第一行包含一个整数 t — 要解决的测试用例数量 (1 ≤ t ≤ 200)。

然后是测试用例。每个测试用例的第一行包含两个整数 n 和 k (1 ≤ n ≤ 200, 1 ≤ k ≤ n)——分别是花园床和水龙头的数量。

下一行包含 k 个整数 xi (1 ≤ xi ≤ n) — 第 i 个水龙头的位置。保证对于每个 $$i \in [2;k]$$ 条件 xi - 1 < xi 成立。

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

请注意,在 hacks 中你必须设置 t = 1。

输出

对于每个测试用例,打印一个整数 - Max 打开某些水龙头后直到整个花园被浇水为止必须经过的最短秒数。

示例

输入 #1

3
5 1
3
3 3
1 2 3
4 1
1

输出 #1

3
1
4

注意

第一个示例包含 3 个测试:

1.有5个花园床,床3上有一个水龙头。如果我们打开它,那么经过1秒后,只有床3会被浇水; 2秒后,床[1, 3]将被浇水,3秒后,所有东西都将被浇水。
2. 有3个花园床,每个花园床都有一个水龙头。如果我们将它们全部打开,那么 1 秒后所有东西都会被浇水。
3. 有 4 个花园床,床 1 中只有一个水龙头。以床 4 为例,浇水需要 4 秒。