Removing Mountains

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 32768/32768 K (Java/Others)

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.

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$.

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

Hint

liuyiding

Source

2017ACM/ICPC广西邀请赛-重现赛(感谢广西大学)

提交代码