P16185 [LBA-OI R1 B] 战术突破

在 LBA 季后赛的关键回合中，教练组设计了一套动态战术板，现在需要进行训练。

用长度为 $n$ 的战术序列 $a$（位置编号 $1$ 到 $n$）模拟进攻路线。你作为控球后卫从起始位置 $1$ 出发，每次可选择以下两种突破方式： ::::info[突破选择]{open} - 长传快攻：若你当前处于战术位 $i$，可消耗 $\dfrac{j}{a_i}$ 秒将球传到 $i+j$ 位（$1\le j\le a_i$），此时你处于 $i+j$ 位。 - 战术换位：由于这是有神力的火星 LBA，可以直接消耗 $1$ 秒切换到位置 $k$，但位置 $k$ 需满足以下条件： 1. $i\le k$。 2. $a_i=a_k$。 3. $\forall j,i

输入共两行： 第一行一个正整数 $n$，表示战术序列长度。 第二行 $n$ 个正整数 $a_i$，表示战术序列。

输出一行两个正整数 $a, b$，满足 $a, b$ 互质且答案为 $\dfrac{a}{b}$。

### 样例解释 样例一的最优解如下： - 花费 $1$ 秒从第 $1$ 位前往第 $2$ 位； - 花费 $1$ 秒从第 $2$ 位前往第 $3$ 位； - 花费 $\frac{1}{4}$ 秒从第 $3$ 位前往第 $4$ 位； - 花费 $\frac{2}{5}$ 秒从第 $4$ 位前往第 $6$ 位。 共耗时 $\frac{53}{20}$ 秒，输出 `53 20`。 样例二的最优解如下： - 花费 $1$ 秒从第 $1$ 位前往第 $6$ 位； 共耗时 $1$ 秒，输出 `1 1`。 ### 数据规模 对于 $100 \%$ 的数据：$1 \le n \le 5 \times 10^6$，$1 \le a_i \le 9$。 ::cute-table |测试点|$n$ |特殊性质| |:-:|:--------:|:--:| |$1$ |$\le 20$ | 无 | |$2$ |^ |^ | |$3$ |$\le 3000$|^ | |$4$ |$\le 5 \times 10^4$|^ | |$5$ |^ |^ | |$6$ |无特殊限制|A | |$7$ |^ |B | |$8$ |^ |无 | |$9$ |^ |^ | |$10$ |^ |^ | 特殊性质 A：$\forall i \in [1, n],a_i = 1$。 特殊性质 B：$\forall i \in [1, n],a_i = k$，其中 $1 \le k \le 9$。 **请注意常数因子对程序效率的影响。**