問題文

クリスマスの飾りつけとして、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

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 になります。