AT_abc469_f [ABC469F] GCD Maximum Spanning Tree

長さ $ N $ の正整数列 $ A $ が与えられます。 $ N $ 頂点の重み付き完全無向グラフがあります。 各頂点には $ 1,2,\dots,N $ の番号が付いています。 $ 1 \leq i \lt j \leq N $ を満たす $ i,j $ について、頂点 $ i $ と頂点 $ j $ を結ぶ辺の重みは $ A_i $ と $ A_j $ の最大公約数です。 このグラフの全域木に含まれる辺の重みの総和としてあり得る値の最大値を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ A_1 $ $ A_2 $ $ \dots $ $ A_N $

答えを $ 1 $ 行で出力せよ。

### Sample Explanation 1 完全グラフには以下の $ 3 $ 本の辺が張られています。 - 頂点 $ 1 $ と頂点 $ 2 $ を結ぶ重み $ 2 $ の辺 - 頂点 $ 1 $ と頂点 $ 3 $ を結ぶ重み $ 4 $ の辺 - 頂点 $ 2 $ と頂点 $ 3 $ を結ぶ重み $ 6 $ の辺 $ 2 $ 本目の辺と $ 3 $ 本目の辺を選ぶと重みの総和は $ 10 $ になり、これがあり得る最大値です。 ### Constraints - $ 2 \leq N \leq 2 \times 10^5 $ - $ 1 \leq A_1 \lt A_2 \lt \dots \lt A_N \leq 10^6 $ - 入力される値はすべて整数