AT_abc469_f [ABC469F] GCD Maximum Spanning Tree

You are given a sequence of positive integers $ A $ of length $ N $ . There is a weighted complete undirected graph with $ N $ vertices. The vertices are numbered $ 1,2,\dots,N $ . For $ i $ and $ j $ satisfying $ 1 \leq i \lt j \leq N $ , the weight of the edge connecting vertices $ i $ and $ j $ is the greatest common divisor of $ A_i $ and $ A_j $ . Find the maximum possible value of the sum of the weights of the edges included in a spanning tree of this graph.

The input is given from Standard Input in the following format: > $ N $ $ A_1 $ $ A_2 $ $ \dots $ $ A_N $

Output the answer in one line.

### Sample Explanation 1 The complete graph has the following three edges. - The edge connecting vertices $ 1 $ and $ 2 $ with weight $ 2 $ - The edge connecting vertices $ 1 $ and $ 3 $ with weight $ 4 $ - The edge connecting vertices $ 2 $ and $ 3 $ with weight $ 6 $ Choosing the second and third edges gives a sum of weights of $ 10 $ , which is the maximum possible value. ### Constraints - $ 2 \leq N \leq 2 \times 10^5 $ - $ 1 \leq A_1 \lt A_2 \lt \dots \lt A_N \leq 10^6 $ - All input values are integers.