CF2026B Black Cells

给你一条被分成若干格子的带子，这些格子从左到右编号为 $0$ 到 $10^{18}$。最初，所有格子都是白色的。 你可以进行如下操作：选择两个白色格子 $i$ 和 $j$，要求 $i \ne j$ 且 $|i - j| \le k$，然后将它们涂成黑色。 给定一个列表 $a$，其中的所有格子都必须被涂成黑色。此外，最多还可以有一个不在该列表中的格子也被涂成黑色。你的任务是确定最小的 $k$ 值，使得可以完成上述要求。

第一行包含一个整数 $t$（$1 \le t \le 500$），表示测试用例的数量。 每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2000$）。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$0 < a_i < 10^{18}$；$a_i < a_{i + 1}$）。 输入的额外约束：所有测试用例中 $n$ 的总和不超过 $2000$。

对于每个测试用例，输出一个整数，表示能够完成要求的最小 $k$ 值。

在第一个样例中，当 $k=1$ 时，可以涂黑格子 $(1, 2)$。 在第二个样例中，当 $k=1$ 时，可以涂黑格子 $(7, 8)$。 在第三个样例中，当 $k=2$ 时，可以涂黑格子 $(2, 4)$ 和 $(8, 9)$。 在第四个样例中，当 $k=3$ 时，可以涂黑格子 $(0, 1)$、$(5, 8)$ 和 $(10, 13)$。 由 ChatGPT 4.1 翻译