题目描述

意大利的切塞纳蒂科 (Cesenatico) 是一座面向亚得里亚海的港口城市，并以拥有运河而闻名。运河中停泊着船只，也作为旅游景点而闻名。这里，我们想要考虑一个将现实简化后的如下情境设定。

运河是直线状的，并且只有一侧与亚得里亚海相通。另外，运河中停泊着从 1 到 $N$ 编号的 $N$ 艘船，船 $i$ ($1 \le i \le N$) 停泊在距离亚得里亚海 $A_i$ 的位置。

这里，编号较小的船停泊在离亚得里亚海更近的位置。也就是说，成立 $A_1 < A_2 < \dots < A_N$。

你决定为了城里举办的祭典给船上色。具体来说，对每一艘船，从颜色 1 到颜色 $N$ 的 $N$ 种颜色中选择 1 种颜色，并用该颜色给船上色。这里，希望满足以下条件。

• 对于任意颜色 $c$ ($1 \le c \le N$)，被涂成颜色 $c$ 的船的数量不是 1 艘。注意，也可以不存在被涂成颜色 $c$ 的船。
• 若被涂成颜色 $c$ 的船有 2 艘以上，则被涂成颜色 $c$ 的船等间隔排列。换句话说，对被涂成颜色 $c$ 的船，将其到亚得里亚海的距离按升序排列得到的序列是等差数列。

为了让船看起来更美观，定义如下所表示的美丽度。

• 在同一种颜色涂装的不同两艘船之间的距离中可能的最小值。这里，船 $i$ 与船 $j$ ($1 \le i \le N,\ 1 \le j \le N,\ i \ne j$) 之间的距离定义为 $|A_i - A_j|$。

给定船的信息时，请编写程序判断是否存在满足条件的船的涂色方式；若存在，则求出作为美丽度可能的最大值。

输入格式

输入以如下形式给出。

$N$
$A_1\ \ A_2\ \ A_3\ \ \dots\ \ A_N$

输出格式

若不存在满足条件的船的涂色方式，则输出 $-1$。

若存在，输出一行：美丽度可能的最大值。

2  
1 2

1

3  
1 10 100

-1

5  
5 6 8 9 11

3

提示

样例解释

样例 $1$ 解释

例如，作为不满足条件的船的涂色方式，可以考虑如下。

• 将船 1 涂成颜色 1，将船 2 涂成颜色 2。

在这种涂色方式中，被涂成颜色 1 的船的数量为 1 艘，因此不满足条件。

例如，作为满足条件的船的涂色方式，可以考虑如下。

• 将船 1 与船 2 涂成颜色 2。

在这种涂色方式中，不存在被涂成颜色 1 的船，因此满足关于颜色 1 的条件。另外，将被涂成颜色 2 的船到亚得里亚海的距离按升序排列得到的序列为 $(1, 2)$，这是等差数列，因此满足关于颜色 2 的条件。于是，这种涂色方式满足条件。

在这种涂色方式中，同色涂装的两艘船的组合是船 1 与船 2。这两艘船之间的距离为 $|A_1 - A_2| = |1 - 2| = 1$。因此，美丽度为 1。

由于无法使美丽度达到 2 以上，因此输出 1。

该输入示例满足所有子任务的约束。

样例 $2$ 解释

为了对任意颜色都使得被涂成该颜色的船的数量不是 1 艘，必须将船 1、2、3 涂成同一种颜色。

此时，将与船 1 被涂的颜色相同的船到亚得里亚海的距离按升序排列得到的序列为 $(1, 10, 100)$，这不是等差数列。

因此，不存在满足条件的船的涂色方式，所以输出 $-1$。

该输入示例满足子任务 2、3、4、5 的约束。

样例 $3$ 解释

例如，作为满足条件的船的涂色方式，可以考虑如下。

• 将船 1、船 3、船 5 涂成颜色 1，将船 2、船 4 涂成颜色 4。

在这种涂色方式中，同色涂装的两艘船的组合共有 4 组，分别是船 1 与船 3、船 1 与船 5、船 2 与船 4、船 3 与船 5。这些组合中两艘船之间的距离分别为 3、6、3、3。因此，美丽度为 3。

由于无法使美丽度达到 4 以上，因此输出 3。

该输入示例满足子任务 2、3、4、5 的约束。

约束

• $2 \le N \le 3\,500$。
• $1 \le A_i \le 10^9$ ($1 \le i \le N$)。
• $A_i < A_{i+1}$ ($1 \le i \le N-1$)。
• 输入的值全部为整数。

子任务

• (8 分) $A_i = i$ ($1 \le i \le N$)。
• (11 分) $N \le 7$。
• (12 分) $N \le 100$。
• (39 分) $N \le 700$。
• (30 分) 没有额外约束。