题目描述

现在是冬天，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]$ 会被浇水；只有在 $2$ 秒正好过去时，区间 $[x_{i}-2, x_{i}+2]$ 才刚好被浇水。

测试样例 $1$ 的花园。白色代表没有水龙头的花坛，红色代表有水龙头的花坛。
打开水龙头后经过 $2$ 秒的花园。白色代表未被浇水的花坛，蓝色代表已被浇水的花坛。

Max 想要在同一时刻打开所有水龙头，他想知道，从打开龙头开始，至少需要多少秒，才能让整个花园都被浇到水。请帮他计算出答案！

输入格式

第一行包含一个整数 $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$ 个水龙头所在的花坛位置。保证对于每个 $i$ 有 $x_{i-1}<x_{i}$。

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

注意，在 hack 时需要设置 $t=1$。

输出格式

对于每组测试用例，输出一个整数，表示 Max 打开水龙头后，最少需要多少秒，才能让整个花园被浇到水。

说明/提示

第一个样例有三个测试用例：

1. 有 $5$ 个花坛，第 $3$ 个花坛有一个水龙头。如果我们打开它，$1$ 秒后只有第 $3$ 个花坛被浇水；$2$ 秒后区间 $[1,3]$ 的花坛被浇水，$3$ 秒后所有花坛都被浇水。
2. 有 $3$ 个花坛，每个花坛上都有一个水龙头。如果同时打开所有水龙头，则 $1$ 秒后所有花坛都被浇水。
3. 有 $4$ 个花坛，只有第 $1$ 个花坛有一个水龙头。要让第 $4$ 个花坛被浇水，需要 $4$ 秒。

由 ChatGPT 5 翻译

样例

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

3
1
4