题目描述

長さ $N$ の正整数列 $A=(A_1,A_2,\dots,A_N)$ が与えられます。

あなたは以下の操作を $A$ の長さが $1$ になるまで繰り返します。

• 操作を行う時点での $A$ の長さを $k$ とする。$ \max(\{A_1,A_2,\dots,A_{k}\})=A_i,\min(\{A_1,A_2,\dots,A_{k}\})=A_j $ かつ $i\ \neq\ j$ を満たす整数の組 $(i,j)$ を選び、$A_i$ を $(A_i\ \bmod\ A_j)$ で置き換える。このとき、$A_i=0$ となったのであれば $A$ から $A_i$ を削除する。

どのように操作を行っても操作回数は一定であることが証明できます。操作回数を求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $A_1$ $A_2$ $\dots$ $A_N$

输出格式

答えを出力せよ。

题目大意

有一个长度为$n$的正整数序列$A=(A_1,A_2,...,A_N)$。

重复以下操作直到序列$A$的长度变为$1$。

• 设$k$为操作前序列$A$的长度.选择整数$i$和$j$,使$A_i$为序列$A$中的最大值，$A_j$为序列$A$中的最小值，且$i≠j$。然后，用$(A_i \bmod A_j)$替换$A_i$。如果$A_i$的值在操作后变为$0$，从序列$A$中删除$A_i$.

请求出需要执行的操作的数量。我们可以证明，在操作中无论如何选择$i,j$，操作的总数是不变的

3
2 3 6

3

6
1232 452 23491 34099 57341 21488

12

提示

制約

• $2\ \le\ N\ \le\ 2\ \times\ 10^5$
• $1\ \le\ A_i\ \le\ 10^9$
• 入力は全て整数である。

Sample Explanation 1

以下のように操作を行うことになります。操作回数は $3$ 回です。 - $i=3,j=1$ を選ぶ。$A_3=0$ となるため、$A$ から $A_3$ を削除する。$A=(2,3)$ となる。 - $i=2,j=1$ を選ぶ。$A_2=1$ となる。$A=(2,1)$ となる。 - $i=1,j=2$ を選ぶ。$A_1=0$ となるため、$A$ から $A_1$ を削除する。$A=(1)$ となる。$A$ の長さが $1$ になったため、操作を終了する。