You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

经过数日的航行，海盗船终于抵达了亡灵岛。

天色昏暗，浓雾弥漫，海风夹带着腐朽的气息，仿佛每一寸空气都充满了阴冷与危险。猪大和猪二站在船头，望着远方那座阴森的岛屿。岛屿周围被一片黑暗森林所环绕，古老的树木枝繁叶茂，树干扭曲如同鬼影重重，每一棵都像是一个个张牙舞爪的恶魔。

小猪们迅速跳下船，踏上这片诡异的土地。“到了，三弟就在这岛上，这片森林被称为死亡森林，我们得格外小心。”猪大语气严肃。“是啊，岛上看起来阴森恐怖，真不知道会有什么等着我们。”猪二也不禁打了个寒战。猪大咬紧牙关：“别怕，三弟就在前方，我们一定要把他救出来！”

小猪们每一步踩在湿滑的泥土上，都发出令人毛骨悚然的回声。周围的树林静得出奇，仿佛连风都不敢在这里流动。树木间的阴影愈发深重，光线被遮挡得几乎全无。树枝缠绕在一起，仿佛无形的锁链，把他们的前行一步步阻隔。猪二一边警惕地四下打量，一边低声说道：“这森林太诡异了，我们得加快脚步。”

走了好一会儿，树林终于开始稀疏，前方豁然开朗，一座巍峨的城堡出现在眼前。城堡古老且阴森，仿佛沉睡了几个世纪，墙壁上爬满了藤蔓，绿色的藤蔓如同触手一般缠绕着城堡的每一寸墙面。城堡的窗户深邃而幽暗，从中透出诡异的绿光，像一双双鬼魅般的眼睛，紧紧盯着他们，令人不寒而栗。

猪二忍不住打了个寒战：“这地方看起来不太对劲，难道三弟就被关在里面？”猪大的眼中闪过一丝坚定：“不管前方多么危险，三弟就在这座暗影城堡里面，我们不能退缩。”它们走近城堡的大门，发现门被厚重的石块堵住，完全无法推开。猪二急忙伸手去摸石门的缝隙，试图找到突破口：“怎么打开这个门？”

就在这时，猪大突然注意到大门旁边有一个奇怪的石头阵，阵法复杂而古老，石头排列成一圈，中央有一个凹陷的槽口，看上去像是某种机关。猪二走过去，蹲下身仔细打量：“这是什么东西？看起来像是一个谜题。”猪大也蹲下，仔细观察周围的石头阵：“这石头阵需要用水来激活。看这里的槽口，好像需要水才能启动这个机关，可能是用来打开大门的。”

题目描述

石头阵的槽口呈线性条带形，从左到右编号依次为$0$到$10^{18}$。所有槽口在初始时均为干燥。

你可以执行以下操作：选择两个空槽口$i$和$j$，使得$i\ne j$且$\vert i-j\vert \le k$，并将槽口$i$与$j$浇水。

给定序列$a$，该序列中的所有槽口必须都被浇水，最多只能一个不在此序列中的槽口被浇水。你的任务是帮小猪兄弟确定使这一切成为可能的最小值$k$。

题目格式

题目输入

第一行包含一个整数$T(1\le T\le 10^3)$，代表测试样例组数。对于每组测试用例：

• 第一行包含一个整数$n(1\le n\le 2\times 10^3)$。
• 第二行包含$n$个整数$a_1,a_2,\cdots,a_n(0\le a_i\le 10^{18},a_i<a_{i+1})$。

题目保证所有测试用例中$\sum n\le 2\times 10^3$。

题目输出

对于每个测试用例，输出一个整数$k$，表示所有给定单元被浇水的最小值。

题目样例

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

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)$。

系列简介

《加勒比海的猪兄弟》是由@主编的一部短篇冒险小说，故事讲述了在加勒比海的波涛之间，勇敢的海盗猪三兄弟展开了一段充满奇遇与挑战的冒险旅程。在骷髅海的军团袭击、亡灵岛的神秘城堡与肥猪黑心实验厂的险象环生中，他们齐心协力，克服了种种危险。在历尽艰难险阻后，三兄弟终于找到了属于自己的平静与幸福。本小说共4章，环环相扣，引人入胜。

本系列题目：