P14800 [JOI 2026 二次预选] 船 / Ship

意大利的切塞纳蒂科 (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$。 若存在，输出一行：美丽度可能的最大值。

### 样例解释 #### 样例 $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 分) 没有额外约束。