← 返回题目列表

Codeforces · 2026/B

B. 黑色电池

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

您将获得一条分为多个单元格的条带,从左到右从 $$$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$$$ 的最小值,可以将所有给定单元格涂成黑色。

示例

输入 #1

4
2
1 2
1
7
3
2 4 9
5
1 5 8 10 13

输出 #1

1
1
2
3

注意

在第一个示例中,使用 $$$k=1$$$,可以绘制单元格 $$$(1, 2)$$$。

在第二个示例中,使用 $$$k=1$$$,可以绘制单元格 $$$(7, 8)$$$。

在第三个示例中,使用 $$$k=2$$$,可以绘制单元格 $$$(2, 4)$$$ 和 $$$(8, 9)$$$。

在第四个示例中,使用 $$$k=3$$$,可以绘制单元格 $$$(0, 1)$$$、$$$(5, 8)$$$ 和 $$$(10, 13)$$$。