← 返回题目列表

AtCoder · joi2026_yo2_f

F. 船舶

中文机器翻译题面 查看原题

配点: 100 点

問題文

意大利的切塞纳蒂科是面向亚得里亚海的港口城市,以其运河而闻名。运河里停泊着船只,这里也被誉为旅游胜地。在这里,我想考虑以下情景设置,它简化了现实。

运河是笔直的,只有一侧通向亚得里亚海。还有,在运河里 编号至 1 减去 N 编号最多为 N 有两艘船停泊。 i (1 \leqq i \leqq N) 是距亚得里亚海的距离 A_i 它停泊在很远的地方。

这里,数字越小,船离亚得里亚海越近。也就是说,A_1 < A_2 < \cdots < A_N 成立。

您决定为镇上的节日画一艘船。具体来说,每艘船都有一种颜色。 颜色来自 1 重新绘制为 N 最多 N 从颜色中 1 选择一种颜色并用该颜色绘制船只。在这里,我们希望满足以下条件。

  • 哪种颜色? c (1 \leqq c \leqq N)以及颜色 涂有 c 的船舶数量为 不是 1 隻不是吗.色 c 的船不需要存在请注意。
  • 色 c 的船 2 如果有多于一艘船,则颜色 涂有 c 的船只等间隔排列。换句话说,颜色 对于颜色为 c 的船舶,通过按升序排列船舶距亚得里亚海的距离而创建的序列是算术级数。

为了让船看起来更好,表述如下。美容。

  • 不同的颜色涂成相同的颜色 2 船舶之间可能的最小距离。在这里,船 i 和船 j (1 \leqq i \leqq N,1 \leqq j \leqq N,i \neq j) | A_i - A_j | 。

给定船舶信息,编写一个程序,判断是否有满足条件的船舶涂装方法,如果有,则找到最大可能的美观值。

制約

  • 2 \leqq N \leqq 3\,500.
  • 1 \leqq A_i \leqq 10^9 (1 \leqq i \leqq N).
  • A_i < A_{i + 1} (1 \leqq i \leqq N - 1).
  • 所有输入值都是整数。

小課題

  1. (8 点) A_i = i (1 \leqq i \leqq N).
  2. (11 点) N \leqq 7.
  3. (12 点) N \leqq 100.
  4. (39 点) N \leqq 700.
  5. (30 点)没有额外的限制。

入力

输入按以下格式给出。

N
A_1 A_2 A_3 \cdots A_N

出力

如果没有办法绘制满足条件的船舶, 输出 -1 。如果存在的话,美的最大可能价值 1 以行的形式输出。


入力例 1

2
1 2

出力例 1

1

例如,如果条件是不满意为船舶喷漆的可能方法如下。

  • 船 1 颜色 1 ,船 用 2 颜色 2 绘画。

在这种绘画方法中,颜色 1 的船舶数量为 不是 1 不满足条件,因为它是一艘船。

例如,可以考虑以下方式作为满足条件的船舶的涂装方式。 没有涂有

  • 船 1 和船 2 颜色 2 绘画。

在这种绘画方法中,颜色 1 的船只,所以颜色 满足 1 的条件。还有颜色 将颜色为 2 的船只距亚得里亚海的距离按升序排列形成的列是 (1, 2) ,这是一个算术级数,所以颜色 满足 2 的条件。因此,这种绘画方法满足了条件。

在这种绘画方法中, 2 一群船就是一艘船。 1 和船 2 。这个 2 船舶之间的距离是 |A_1 - A_2| = |1 - 2| = 1 。因此,美就是 1 。

美容 由于它不能大于 2 ,1 。 你只需要砍掉

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


入力例 2

3
1 10 100

出力例 2

-1

对于任何颜色,计算涂有该颜色的船舶数量。 1 为了避免成为一艘船, 您需要用相同的颜色绘制 1, 2, 3 。

此时,船 将标有 1 的船只距亚得里亚海的距离按升序排列形成的柱是 (1, 10, 100) ,这不是算术级数。

因此,既然没有办法绘制满足条件的船舶,-1 。 你只需要砍掉

此输入示例是一个小作业。 2, 3, 4, 5 满足约束。


入力例 3

5
5 6 8 9 11

出力例 3

3

例如,可以考虑以下方式作为满足条件的船舶的涂装方式。 没有涂有

  • 船 1 和船 3 和船 5 颜色 1 ,船 用 2 和船 4 颜色 4 绘画。

在这种绘画方法中, 2 一群船就是一艘船。 1 和船 3,船 1 和船 5,船 2 和船 4,船 3 和船 5 可以得到第 4 设置。在这些对中 2 船舶之间的距离是 3, 6, 3, 3 。因此,美就是 3 。

美容 由于它不能大于 4 ,3 。 你只需要砍掉

此输入示例是一个小作业。 2, 3, 4, 5 满足约束。