配点 : 100 点
問題文
N 由个不同正整数构成的数列 A=(A_1,A_2,\ldots,A_N) 。 对于A 的元素重新排列得到数列 B=(B_1,B_2,\ldots,B_N) 时,求以下值的最小值。
\displaystyle\left\lfloor\frac{B_2}{B_1}\right\rfloor + \left\lfloor\frac{B_3}{B_2}\right\rfloor + \cdots + \left\lfloor\frac{B_{N}}{B_{N-1}}\right\rfloor + \left\lfloor\frac{B_1}{B_N}\right\rfloor
其中,实数 x 反对 \left\lfloor x\right\rfloor 在 x 表示不超过的最大整数。
制約
- 所有输入均为整数
- 2 \leq N \leq 2\times 10^5
- 1 \leq A_i \leq 10^{18}
- A_i\neq A_j (i\neq j)
入力
输入是按以下格式从标准输入给出的。
N A_1 A_2 \ldots A_N
出力
答案 请打印除以 1 行输出。
入力例 1
3 2 3 6
出力例 1
3
(B_1,B_2,B_3) = (6, 2, 3) 以\displaystyle\left\lfloor\frac{B_2}{B_1}\right\rfloor + \left\lfloor\frac{B_3}{B_2}\right\rfloor + \left\lfloor\frac{B_1}{B_3}\right\rfloor = \left\lfloor\frac{2}{6}\right\rfloor + \left\lfloor\frac{3}{2}\right\rfloor + \left\lfloor\frac{6}{3}\right\rfloor = 0 + 1 + 2 = 3 。 对于
入力例 2
2 15 4
出力例 2
3
入力例 3
9 284791808 107902 13660981249408 4622332661 13405199 24590921 361 244448137 16077087227955422
出力例 3
4580