Removing Mountains
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 65 Accepted Submission(s): 6
Problem Description
Long long time ago, there was a foolish man called Yu Gong. One day, he found that the mountains around his house was really troublesome, so he decided to remove them. The work had been doing year in and year out.
It is 2030 now. With the development of technologies, the transportations have been really convenient, so the descendants of Yu Gong don't need to remove these mountains any more. Instead, they want to make the mountains more beautiful. In their opinion, the mountains are beautiful if they have a cyclical character. Furthermore, smaller the repetition period is, greater the mountains they deem.
The mountains can be considered a sequence of positive integers $a_{1},a_{2},...,a_{n}$, each of which indicates an altitude. We say the repetition period of the sequences is $k$ if $k$ is the smallest number which satisfy that for every integer $i$, $k+1 \leq i \leq n$, $a_{i}$ always equals to $a_{i-k}$. For example, the repetition period of the following sequence:1 2 3 2 1 2 3 2 1 2 3 is 4.
Now the descendants of Yu Gong want to the make mountains more beautiful by changing altitude in one position. Please tell them the smallest repetition period after changing altitude and also the number of positions they can choose to change altitude in order to reach the smallest repetition period. Note that they can change any meter (including zero) in one position.
It is 2030 now. With the development of technologies, the transportations have been really convenient, so the descendants of Yu Gong don't need to remove these mountains any more. Instead, they want to make the mountains more beautiful. In their opinion, the mountains are beautiful if they have a cyclical character. Furthermore, smaller the repetition period is, greater the mountains they deem.
The mountains can be considered a sequence of positive integers $a_{1},a_{2},...,a_{n}$, each of which indicates an altitude. We say the repetition period of the sequences is $k$ if $k$ is the smallest number which satisfy that for every integer $i$, $k+1 \leq i \leq n$, $a_{i}$ always equals to $a_{i-k}$. For example, the repetition period of the following sequence:1 2 3 2 1 2 3 2 1 2 3 is 4.
Now the descendants of Yu Gong want to the make mountains more beautiful by changing altitude in one position. Please tell them the smallest repetition period after changing altitude and also the number of positions they can choose to change altitude in order to reach the smallest repetition period. Note that they can change any meter (including zero) in one position.
Input
There are lots of test cases.
For each test case, the first line contains a positive integer $n$, $1 \leq n \leq 10^6$, denoting the length of the sequence. Next line is the sequence $a_{1},...,a_{n}$, $0 \leq a_{i} \leq 9$. There are no spaces between $a_{i}$ and $a_{i+1}$.
The whole input satisfies $\sum{n} \leq 6 \times 10^6$.
For each test case, the first line contains a positive integer $n$, $1 \leq n \leq 10^6$, denoting the length of the sequence. Next line is the sequence $a_{1},...,a_{n}$, $0 \leq a_{i} \leq 9$. There are no spaces between $a_{i}$ and $a_{i+1}$.
The whole input satisfies $\sum{n} \leq 6 \times 10^6$.
Output
For each test case, output two integers seperated by one space in a line, denoting the answer.
Sample Input
5 32321
Sample Output
2 1