슬롯머신의 주기

슬롯머신은 카지노에서 인기 있는 게임 기계다. 여기서 다루는 슬롯머신에는 그림이 나타나는 자리가 여섯 개 있고, 그림의 조합에 따라 돈을 따거나 잃는다. 그림은 열 종류이므로 그림 하나를 0부터 9까지의 숫자 하나로 나타낸다. 그러면 슬롯머신이 한 번 내놓는 결과는 $w = w_1 w_2 w_3 w_4 w_5 w_6$ ($0 \le w_1, w_2, w_3, w_4, w_5, w_6 \le 9$) 꼴의 여섯 자리 수 하나로 적을 수 있다.

그림 1. 슬롯머신의 배치.

예전 슬롯머신은 기계 부품으로 만들었지만 요즘은 PC 기반 장치가 그 자리를 대신한다. 이 변화는 치명적인 허점을 하나 남겼다. 결과를 유사난수 생성기가 만들어 내므로 결과 수열이 주기를 갖는다는 점이다. 슬롯머신의 $i$번째 결과를 $T[i]$라 하자. 처음에는 길이 $k$인 진짜 무작위 수열 $T[1], T[2], \dots, T[k]$가 나오고, 그 뒤에는 어떤 양의 정수 $p$가 있어서 $i > k$인 모든 $i$에 대해 $T[i+p] = T[i]$가 성립한다. $k$와 $p$를 정확히 알아낸 사람은 좋은 조합이 나올 차례를 미리 알고 큰돈을 걸어 카지노를 이긴다.

관측한 값은 $n$개뿐이므로, 어떤 쌍 $(k, p)$가 조건을 만족한다는 말은 $k < i$이고 $i + p \le n$인 모든 $i$에서 $T[i+p] = T[i]$가 성립한다는 뜻이다. 여기서 $k$는 0 이상의 정수, $p$는 1 이상의 정수다.

예를 들어 결과 수열의 처음 여섯 개가 612534, 3157, 423, 3157, 423, 3157이라고 하자. 앞자리의 0은 적지 않으므로 3157은 003157을, 423은 000423을 뜻한다. 열 번째 값을 알고 싶다면 $k$와 $p$를 정확히 알아야 하는데, 후보가 여럿이다. 한쪽 극단은 $k = 5$, $p = 1$이고 다른 쪽 극단은 $k = 0$, $p = 6$이다. $k$와 $p$가 둘 다 작을수록 그럴듯한 후보이므로 $k + p$가 가장 작은 쌍을 고른다. 그런 쌍이 둘 이상이면 그중 $p$가 가장 작은 것을 고른다. 이 예에서는 $k = 1$, $p = 2$가 답이다.

슬롯머신의 연속된 결과 $T[1], T[2], \dots, T[n]$이 주어진다. 위 기준을 만족하는 $k$와 $p$를 구하는 프로그램을 작성하시오.

첫째 줄에 지금까지 관측한 결과 수열의 길이 $n$ ($1 \le n \le 10^6$)이 주어진다.

둘째 줄에 $n$개의 수 $T[1], T[2], \dots, T[n]$이 공백으로 구분되어 주어진다. 각 수는 0 이상 999999 이하의 정수다.

첫째 줄에 $k$와 $p$를 공백으로 구분해 출력한다.