Period of a Slot Machine

Slot machines are popular game machines in casinos. The machine considered here has six places where a figure appears, and the combination of figures decides whether you win or lose money. There are ten kinds of figures, so each figure is written as a single digit from 0 to 9. One outcome of the machine is then a six-digit number $w = w_1 w_2 w_3 w_4 w_5 w_6$ with $0 \le w_1, w_2, w_3, w_4, w_5, w_6 \le 9$.

Figure 1. The layout of a slot machine.

Old slot machines were built from mechanical parts, but PC based devices have taken their place. That change left one fatal weakness: the outcomes come from a pseudo-random number generator, so the sequence of outcomes is periodic. Let $T[i]$ be the $i$-th outcome of a machine. The sequence starts with a truly random block $T[1], T[2], \dots, T[k]$ of length $k$, and after it there is a positive integer $p$ such that $T[i+p] = T[i]$ for every $i > k$. Anyone who learns the exact values of $k$ and $p$ knows in advance when a good combination is due and beats the casino by betting a lot of money on that round.

Only $n$ outcomes have been observed, so a pair $(k, p)$ satisfies the condition when $T[i+p] = T[i]$ holds for every $i$ with $k < i$ and $i + p \le n$. Here $k$ is an integer with $k \ge 0$ and $p$ is an integer with $p \ge 1$.

For example, suppose the first six outcomes are 612534, 3157, 423, 3157, 423, 3157. Leading zeros are dropped, so 3157 stands for 003157 and 423 stands for 000423. To predict the tenth outcome you need the exact values of $k$ and $p$, and there are many candidates. One extreme is $k = 5$ and $p = 1$, another is $k = 0$ and $p = 6$. A candidate is more plausible when both $k$ and $p$ are small, so take the pair with the smallest $k + p$. If two or more pairs share that value, take the one with the smallest $p$ among them. In this example the answer is $k = 1$ and $p = 2$.

You are given $n$ consecutive outcomes $T[1], T[2], \dots, T[n]$ of a slot machine. Write a program that computes $k$ and $p$ under the rule above.

The first line contains the length $n$ ($1 \le n \le 10^6$) of the outcome sequence observed so far.

The second line contains $n$ numbers $T[1], T[2], \dots, T[n]$ separated by spaces. Each number is an integer between 0 and 999999.

Print $k$ and $p$ on the first line, separated by a space.