Optimal Necklace Cutting

Byteasar has a long string of colorful coral beads represented by positive integers. He possesses a machine that can cut the string into contiguous pieces (substrings) of a given length \(k\). The machine always starts cutting from the beginning of the string and makes cuts every \(k\) beads. If the length of the string is not a multiple of \(k\), the last remaining part (with length less than \(k\)) is discarded.

When considering the pieces, the order of the beads in a piece is not significant up to reversal; that is, a substring \(s = a_1a_2\dots a_k\) is considered identical to its reverse \(s^R = a_k\dots a_2a_1\). In other words, the canonical form of a substring can be taken as the lexicographically smaller of \(s\) and \(s^R\).

Byteasar wonders what value of \(k\) will maximize the number of distinct (canonical) pieces obtained by this process. If more than one value of \(k\) yields the maximum number of distinct pieces, he will choose the smallest such \(k\>.

Your task is to write a program that, given the bead string, determines the optimum value of \(k\) according to Byteasar's criteria.

inputFormat

The first line of input contains an integer \(n\) (the number of beads). The second line contains \(n\) positive integers representing the colors of the beads in the order they appear in the string.

For example:

5
1 2 3 2 1

outputFormat

Output the optimum value of \(k\) that maximizes the number of distinct substrings (under reversal equivalence). In case of a tie, output the smallest \(k\).

For the sample input above, the output should be:

1

sample

5
1 2 3 2 1

1