← 返回题目列表

AtCoder · utpc2023_q

Q. 商和

中文机器翻译题面 查看原题

配点 : 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