意大利的切塞纳蒂科（Cesenatico）是濒临亚得里亚海的港口城市，以其运河闻名。运河中停泊着许多船只，也是一处著名的旅游胜地。现在，我们对现实情况做如下简化建模：

运河是直线的，只有一侧通向亚得里亚海。运河中停泊着 $N$ 艘编号为 $1$ 到 $N$ 的船只，第 $i$ （$1 \leq i \leq N$）艘船停泊在距离亚得里亚海 $A_i$ 的位置上。

编号较小的船离亚得里亚海更近，即 $A_1 < A_2 < \cdots < A_N$。

你需要为即将在本地举办的节日美化船只，对每艘船进行涂色。具体来说，每艘船要从 $1$ 到 $N$ 的 $N$ 种颜色中选择一种，将其涂成该颜色。要求满足以下条件：

• 对于每种颜色 $c$（$1 \leq c \leq N$），用颜色 $c$ 涂色的船只数量不能等于 $1$。注意，用颜色 $c$ 涂色的船只数量可以为 $0$。
• 当用颜色 $c$ 涂色的船只数量不少于 $2$ 时，这些船的停泊位置必须等间隔排列。换句话说，所有用颜色 $c$ 涂色的船按与亚得里亚海的距离从小到大排列后应构成等差数列。

为了让船只看起来更美观，定义“美丽度”为：

• 所有同一种颜色涂色的两艘不同船之间距离的最小值。具体地，设第 $i$、$j$（$1 \leq i,j \leq N$, $i \neq j$）艘船间距离为 $|A_i-A_j|$。

现在给出所有船的具体信息，判断是否存在一种满足条件的涂色方案；如果存在，求所有可能美丽度的最大值。

输入为以下形式：

$N$ $A_1$ $A_2$ $A_3$ $\cdots$ $A_N$

若不存在满足条件的涂色方案，输出 -1。否则，输出一个整数，代表最大的美丽度。

子任务

1. （8 分）$A_i=i$（$1\leq i\leq N$）。
2. （11 分）$N\leq7$。
3. （12 分）$N\leq100$。
4. （39 分）$N\leq700$。
5. （30 分）无附加限制。

样例解释 1

比如，下面这种不满足条件的涂色方案：

• 将船 $1$ 涂为颜色 $1$，将船 $2$ 涂为颜色 $2$。

这个方案下，颜色 $1$ 用于涂色的船仅有 $1$ 艘，不满足条件。

又如，以下方案是满足条件的：

• 将船 $1$、$2$ 都涂成颜色 $2$。

此时，颜色 $1$ 没有被用于任何船，依然满足条件。颜色 $2$ 涂色的船位置序列为 $(1,2)$，这是一组等差数列，也满足条件。因此该方案满足题意。

在这个方案下，同色的船有一组（船 $1,2$）。它们之间的距离为 $|A_1-A_2|=|1-2|=1$，所以美丽度为 $1$。

不能得到更大的美丽度，因此输出 $1$。

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

样例解释 2

对于每个颜色，都不能“只涂一艘”。那么，必须把船 $1,2,3$ 都染成同一种颜色。

此时，这些船的距离序列为 $(1,10,100)$，并非等差数列。

也就是说，不存在可行涂色方案，输出 $-1$。

该输入样例满足子任务 $2,3,4,5$ 的约束。

样例解释 3

例如，下面的涂色方案是满足条件的：

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

此时，同色船的两两组合为：$1$ 和 $3$、$1$ 和 $5$、$2$ 和 $4$、$3$ 和 $5$，共 $4$ 组。它们的距离分别是 $3,6,3,3$。因此美丽度为 $3$。

无法得到更大的美丽度，所以输出 $3$。

该输入样例满足子任务 $2,3,4,5$ 的约束。

约束条件

• $2 \leq N \leq 3\,500$。
• $1 \leq A_i \leq 10^9$（$1 \leq i \leq N$）。
• $A_i < A_{i+1}$（$1 \leq i \leq N-1$）。
• 所有输入均为整数。

由 ChatGPT 5 翻译