Sum of Pairwise LCMs

Given an array of integers \( A_1, A_2, \ldots, A_N \), compute the value of the expression

\[ S = \sum_{i=1}^N \sum_{j=1}^N \mathrm{lcm}(A_i, A_j)\]

where \(\mathrm{lcm}(a,b)\) denotes the least common multiple of \(a\) and \(b\). Use the formula \[ \mathrm{lcm}(a,b) = \frac{a \times b}{\gcd(a,b)} \] provided that \(\gcd(a,b)\) is the greatest common divisor of \(a\) and \(b\).

inputFormat

The first line contains a single integer \(N\) (1 \(\leq N \leq 10^5\)) representing the number of elements in the array. The second line contains \(N\) positive integers \(A_1, A_2, \ldots, A_N\) separated by spaces.

outputFormat

Output a single integer, the value of \(S = \sum_{i=1}^N \sum_{j=1}^N \mathrm{lcm}(A_i, A_j)\).

sample

1
1

1