← 返回题目列表

AtCoder · pakencamp_2018_day2_c

C. 圣诞装饰品

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

配点: 100 点

問題文

圣诞节, 决定把N 个装饰物排成一列。
装饰品的颜色(例如,红色、蓝色、金色等)有 N 种,每种都有编号 1, 2, ..., N 分配。
从左边开始 i 个装饰品决定使用编号为 a_i 的颜色来装饰。但是,尚未确定颜色的装饰品,a_i = 0 将会表示为。

你希望尽可能缩短圣诞装饰的“周期”。
圣诞装饰的“周期”定义如下。

  • 从左数起最初的 X 个装饰物的颜色,之后也重复出现(但最后部分可以不完整) X 中最小的 X 就是“周期”。
  • 也就是说,从左开始 i 号装饰的颜色是 p_i 时,所有 i (1 \leq i \leq N-X) 中 如果 p_i = p_{i+X} 的 X 中最小的 X 就是“周期”。
  • 例如,p = (1, 3, 2, 1, 3, 2, 1, 3) 的情况为“周期” = 3、p = (1, 3, 5, 5, 5, 1, 3, 5, 5) 的情况为“周期” = 5 。另外,当所有颜色相同时,为了使“周期” = 1 。

最小,决定尚未决定的装饰颜色时,请求出“周期”的值会是多少。

制約

  • N 是 1 以上 2 \ 019 的整数 给出了
  • 0 \leq a_i \leq N

入力

输入将以以下格式从标准输入给出。

N
a_1 a_2 a_3 ... a_N

出力

作为装饰的“周期”可以考虑的最小值,请输出一行。

小課題

小課題 1 [10 点]

  • N \leq 3 很满意。

小課題 2 [30 点]

  • a_i \neq 0 很满意。

小課題 3 [30 点]

  • N \leq 50 很满意。

小課題 4 [30 点]

  • 没有额外否定。

入力例 1

11
1 2 3 0 2 3 1 0 3 1 0

出力例 1

3

圣诞装饰的 4 番目、8 番目、11 号装饰的颜色尚未决定。如果将它们的颜色编号分别设为 1, 2, 2 ,则会形成如下装饰
(1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2)
。这是,周期为 3 。没有比这更小的周期的颜色决定方法。3 是答案。


入力例 2

3
2 2 3

出力例 2

3

所有的颜色都已确定,这种装饰的周期是 3 。
另外,这个输入例是小课题 1, 2 满足双方的否定。


入力例 3

13
12 2 0 0 2 0 0 2 4 12 0 4 0

出力例 3

3

装饰的颜色编号 (12, 2, 4, 12, 2, 4, 12, 2, 4, 12, 2, 4, 12) 时,周期是 3 。