迈克正在尝试攀岩,但他很糟糕。
墙上有 n 个据点,第 i 个据点位于距地面高度 ai 处。另外,让序列ai递增,即对于所有i从1到n-1,ai < ai + 1;我们将这样的序列称为轨道。 Mike 认为轨道 a1, ..., an 的难度为 $$d = \max_{1 \leq i \leq n-1} (a_{i+1} - a_i)$$。换句话说,难度等于高度相邻的两个点之间的最大距离。
今天,迈克决定用悬挂在高度 a1, ..., an 上的支撑点覆盖赛道。为了让问题变得更难,Mike 决定去掉一个保留,即去掉序列中的一个元素(例如,如果我们取出序列 (1, 2, 3, 4, 5) 并从中去掉第三个元素,我们就得到序列 (1, 2, 4, 5))。然而,由于 Mike 的攀爬能力很差,他希望在所有可能的移除抓点的选项中,最终的难度(即移除抓点后相邻抓点之间的最大高度差)尽可能小。第一个和最后一个保持点必须保持在原来的位置。
帮助 Mike 确定取消一次抓握后赛道的最低难度。
输入
第一行包含一个整数 n (3 ≤ n ≤ 100) — 保持次数。
下一行包含 n 个空格分隔的整数 ai (1 ≤ ai ≤ 1000),其中 ai 是保持编号 i 悬挂的高度。序列 ai 正在增加(即除了第一个元素之外的每个元素都严格大于前一个元素)。
输出
打印单个数字 — 取消单个保持后轨道的最低难度。
示例
输入 #1
3 1 4 6
输出 #1
5
输入 #2
5 1 2 3 4 5
输出 #2
2
输入 #3
5 1 2 3 7 8
输出 #3
4
注意
在第一个样本中,您可以仅删除第二个保留,则序列看起来像 (1, 6),相邻元素的最大差值等于 5。
在移除每个握点后的第二个测试中,难度等于 2。
在第三个测试中,您可以获得序列(1,3,7,8)、(1,2,7,8)、(1,2,3,8),其难度分别为4、5和5。因此,删除第二个元素后,我们得到最佳答案——4。