春節の前夜、ミッキーは時計塔で一台のレピーター（復読機）を拾いました。このレピーターは自動的に繰り返すだけでなく、数列に含まれるすべての数の最大公約数を求めるためにも使えます。

この機械の使い方は以下の通りです。まず、長さ $n$ の数列を入力します。$i$ 番目の数を $a_i$ ($1 \le i \le n$) とします。

毎回、ミッキーは隣り合う2つの数 $a_i, a_{i+1}$ を選び、その和である $a_i + a_{i+1}$ に等しい枚数の金貨を機械に投入します。すると、機械は自動的にこれら2つの数の最大公約数を計算し、その2つの隣り合う数をその最大公約数で置き換えます。置き換えは元の2つの数があった位置で行われます。この操作を繰り返し、機械の中の数列が残り1つになるまで続けます。この残った数が答えとなります。

「レピーターの修理工になりたくない金持ちのネズミは、良い数学者ではない」という言葉があるように、ミッキーは答えを算出するために必要な金貨の最小枚数を知りたいと考えています。

入力

1行目に正整数 $n$ が与えられ、数列の長さを表します。

2行目に $n$ 個の正整数 $a_i$ が与えられ、数列を表します。

出力

最小の金貨使用枚数を表す整数を1行で出力してください。

入出力例

入力 1

7
33 33 66 6 66 22 22

出力 1

260

注記 1

最初、数列は $[33, 33, 66, 6, 66, 22, 22]$ です。

1手目：$a_4, a_5$ を統合し、$[33, 33, 66, 6, 22, 22]$ を得ます。

2手目：$a_4, a_5$ を統合し、$[33, 33, 66, 2, 22]$ を得ます。

3手目：$a_3, a_4$ を統合し、$[33, 33, 2, 22]$ を得ます。

4手目：$a_2, a_3$ を統合し、$[33, 1, 22]$ を得ます。

5手目：$a_1, a_2$ を統合し、$[1, 22]$ を得ます。

6手目：$a_1, a_2$ を統合し、$[1]$ を得ます。

総コストは $(6 + 66) + (6 + 22) + (66 + 2) + (33 + 2) + (33 + 1) + (1 + 22) = 260$ となります。

入力 2

サンプルデータダウンロードを参照してください。

出力 2

サンプルデータダウンロードを参照してください。

制約

すべてのデータにおいて、$1\le n\le 2\times 10^5, 1\le a_i \le 10^{12}$ を満たします。