老虎机是赌场中常见的博彩机器。我们所考虑的老虎机有六个显示数字的位置。通过数字的组合，玩家可能会赢钱或输钱。数字共有十种，因此我们用一个六位数 $w = w_1w_2w_3w_4w_5w_6$ 来表示老虎机的一种可能结果，其中 $0 \le w_1, w_2, w_3, w_4, w_5, w_6 \le 9$。保证结果永远不会出现 $000000$。

图 I.1. 老虎机的布局。

旧式老虎机由机械部件组成，但如今它们已被基于计算机的系统所取代。这种转变带来了一个关键缺陷：它们基于伪随机数生成器，因此老虎机的结果序列是周期性的。设 $T[i]$ 为第 $i$ 个结果。起初，这是一个真正的随机序列，长度为 $k$，$T[1], T[2], \dots, T[k]$。随后存在一个正整数 $p$，使得对于所有 $i > k$，$T[i + p] = T[i]$。一旦攻击者能够找出 $k$ 和 $p$ 的确切值，他或她就可以通过提前预知结果并下注大量赌注来战胜赌场。

例如，假设你拥有前六个结果序列：$612534, 3157, 423, 3157, 423$ 以及 $3157$。注意，我们可以去掉前面的 $0$。因此，$3157$ 代表 $003157$，而 $423$ 代表 $000423$。你想知道第十个数字。如果你知道 $k$ 和 $p$ 的确切值，你就可以预测第十个数字。然而，$k$ 和 $p$ 有许多候选值：一种极端情况是 $k=5$ 且 $p=1$，另一种是 $k=0$ 且 $p=6$。最可能的候选者是 $k$ 和 $p$ 都较小的情况。因此，我们的选择是 $k+p$ 最小的那一个。如果有两个或更多这样的候选者，我们选择 $p$ 最小的那一个。在我们的例子中，经过一些繁琐的计算，我们得到 $k=1$ 且 $p=2$。

假设你拥有老虎机的 $n$ 个连续结果 $T[1], T[2], \dots, T[n]$。编写一个程序来计算满足上述条件的 $k$ 和 $p$ 的值。

输入格式

程序从标准输入读取数据。第一行包含一个正整数 $n$ ($1 \le n \le 1,000,000$)，表示到目前为止在结果序列中观察到的数字个数。接下来的行包含 $n$ 个数字。这些数字中的每一个都在 $0$ 到 $999,999$ 之间。

输出格式

程序将结果写入标准输出。在一行中打印两个整数 $k$ 和 $p$。

样例

样例输入 1

6
612534 3157 423 3157 423 3157

样例输出 1

1 2

样例输入 2

9
1 2 1 3 1 2 1 3 1

样例输出 2

0 4