Description

For $A_1, A_2, \cdots, A_N$, compute the following value.

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

Here, $\mathrm{lcm}(a, b)$ denotes the least common multiple of $a$ and $b$.

Input Format

The first line contains an integer $N$.

The second line contains $N$ integers $A_1, A_2, \cdots, A_N$.

Output Format

Output one integer in a single line, representing the required value.

2
2 3

17

Hint

Constraints:

• For 30% of the testdata, $1 \le N \le 1000$, $1 \le A_i \le 5 \times 10^4$.
• For another 30% of the testdata, $1 \le N \le 5 \times 10^4$, $1 \le A_i \le 1000$.
• For 100% of the testdata, $1 \le N \le 5 \times 10^4$, $1 \le A_i \le 5 \times 10^4$.

Translated by ChatGPT 5