#214912. [JOI 2026 二次预选] 船 / Ship

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

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

这里，编号较小的船停泊在离亚得里亚海更近的位置。也就是说，成立 。

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

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

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

• 在同一种颜色涂装的不同两艘船之间的距离中可能的最小值。这里，船 与船 () 之间的距离定义为 。

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

输入以如下形式给出。

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

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

样例输入 1

2  
1 2

样例输出 1

1

样例输入 2

3  
1 10 100

样例输出 2

-1

样例输入 3

5  
5 6 8 9 11

样例输出 3

3

样例解释

样例 解释

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

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

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

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

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

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

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

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

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

样例 解释

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

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

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

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

样例 解释

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

• 将船 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 的约束。

约束

• 。
• ()。
• ()。
• 输入的值全部为整数。

子任务

• (8 分) ()。
• (11 分) 。
• (12 分) 。
• (39 分) 。
• (30 分) 没有额外约束。