配点: 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 。