Problem Description

As part of Christmas decorations, we decided to arrange $ N $ ornaments in a row.
There are $ N $ types of colors for the ornaments (e.g., red, blue, gold, etc.), each numbered $ 1 $, $ 2 $, ..., $ N $.
The $ i $-th ornament from the left is decided to be decorated with the color numbered $ a_i $. However, for ornaments whose colors have not been decided yet, $ a_i = 0 $ is used to represent them.

You want to make the "period" of the Christmas decorations as short as possible.
The "period" of the Christmas decorations is defined as follows:

• The "period" is the smallest $ X $ such that the colors of the first $ X $ ornaments from the left repeat thereafter (though the last part may be truncated).
• That is, when the color of the $ i $-th ornament from the left is $ p_i $, the "period" is the smallest $ X $ such that $ p_i = p_{i+X} $ for all $ i $ $(1 \leq i \leq N-X)$.
• For example, for $ p = (1, 3, 2, 1, 3, 2, 1, 3) $, the "period" = $ 3 $, and for $ p = (1, 3, 5, 5, 5, 1, 3, 5, 5) $, the "period" = $ 5 $. Also, if all colors are the same, the "period" = $ 1 $.

Determine the value of the "period" when the colors of the undecided ornaments are decided to minimize the "period".

Input Format

The input is given from the standard input in the following format:

$ N $ $ a_1 $ $ a_2 $ $ a_3 $ ... $ a_N $

Output Format

Output the smallest possible value of the "period" of the decorations in one line.

Sample Input and Output

Sample Input #1

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

Sample Output #1

3

Sample Input #2

3
2 2 3

Sample Output #2

3

Sample Input #3

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

Sample Output #3

3

Notes/Hints

Constraints

• $ N $ is an integer between $ 1 $ and $ 2,019 $ inclusive.
• $0 \leq a_i \leq N$

Subtasks

Subtask $ 1 $ \[$ 10 $ points\]

• Satisfies $N \leq 3$.

Subtask $ 2 $ \[$ 30 $ points\]

• Satisfies $a_i \neq 0$.

Subtask $ 3 $ \[$ 30 $ points\]

• Satisfies $N \leq 50$.

Subtask $ 4 $ \[$ 30 $ points\]

• No additional constraints.

Sample Explanation 1

The colors of the $ 4 $-th, $ 8 $-th, and $ 11 $-th ornaments are not decided yet. If we decide their color numbers to be $ 1 $, $ 2 $, and $ 2 $ respectively, the decorations will be as follows: $ (1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2) $. This has a period of $ 3 $. There is no way to decide the colors to get a period less than $ 3 $, so the answer is $ 3 $.

Sample Explanation 2

All colors are decided, and the period of this decoration is $ 3 $. This input example satisfies the constraints of both Subtask $ 1 $ and Subtask $ 2 $.

Sample Explanation 3

If we decide the color numbers of the decorations to be $ (12, 2, 4, 12, 2, 4, 12, 2, 4, 12, 2, 4, 12) $, the period will be $ 3 $.

见题面 Input 部分

见题面 Output 部分