AT_joi2026_yo2_f 船 (Ship)

意大利的切塞纳蒂科（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 翻译