P3498 [POI 2010] KOR-Beads

Byteasar once decided to start manufacturing necklaces. He subsequently bought a very long string of colourful coral beads for a bargain price. Byteasar now also has a machine that, for a given  (), can cut the string into pieces (or substrings) of  coral beads (i.e., the first piece consists of the beads no. , the second of , etc.). If the length of the string (measured in coral beads) is not a multiple of , then the last piece is not used, as it has length smaller than . From now on we denote the colours of the beads with positive integers. Byteasar, always praising diversity, wonders how he should choose the number  in order to get as many different substrings as possible. The ends of the long string that will be cut are different: there are specific beginning and ending (rather than two interchangeable endpoints), and the machine of course starts cutting at the beginning. On the other hand, in the substrings obtained from cutting the endpoints are interchangeable, and so the substrings can be reversed. In other words, the substrings  and  are identical to us. Write a program that determines the optimum value of  for Byteasar.

N/A

N/A

$1≤n≤2\times 10^5$，且 $\forall 1\le i\le n$，有 $1\le a_i\le n$