You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Description

给定一个长度为 $n$ 的序列 $𝑎$，保证 $a_i$ 互不相同，需要你求出所有 $f(i,j), 1\le i\le j\le n$ 的和。

$f(i,j)$ 表示去掉 $i$ 到 $j$ 的所有数后剩余数($a_1,a_2,...,a_{i-1}, a_{j+1},a_{j+2},...,a_n$)中任取两个数字的最大 gcd。若剩余数不足两个则 $f(i,j)=0$。

Input

The first line of the input contains a single integer n (1 ≤ n ≤ 200 000) — the number of elements in a.

The next line contains n integers a_i (1 ≤ a_i ≤ 200 000), where the i-th number is equal to the i-th element of the array a. It is guaranteed that all a_i are distinct.

Output

Print a single line containing the value of ultimate weirdness of the array a.

3
2 6 3

6

Note

Consider the first sample.

• f(1,  1) is equal to 3.
• f(2,  2) is equal to 1.
• f(3,  3) is equal to 2.
• f(1,  2), f(1,  3) and f(2,  3) are equal to 0.