CF671C.Ultimate Weirdness of an Array

Yasin has an array a containing n integers. Yasin is a 5 year old, so he loves ultimate weird things.

Yasin denotes weirdness of an array as maximum gcd(a__i,  a__j) value among all 1 ≤ i < j ≤ n. For n ≤ 1 weirdness is equal to 0, gcd(x,  y) is the greatest common divisor of integers x and y.

He also defines the ultimate weirdness of an array. Ultimate weirdness is where f(i,  j) is weirdness of the new array a obtained by removing all elements between i and j inclusive, so new array is [_a_1... a__i - 1, a__j + 1... a__n].

Since 5 year old boys can't code, Yasin asks for your help to find the value of ultimate weirdness of the given array a!

亚辛有一个包含 $n$ 个整数的数组 $a$。亚辛今年 5 岁，因此他酷爱极致古怪的事物。

亚辛将一个数组的“古怪度”（weirdness）定义为所有满足 $1 \leq i < j \leq n$ 的下标对 $(i, j)$ 中 $\gcd(a_i,\, a_j)$ 的最大值。当 $n \leq 1$ 时，古怪度定义为 $0$；其中 $\gcd(x,\, y)$ 表示整数 $x$ 和 $y$ 的最大公约数。

他还定义了数组的“极致古怪度”（ultimate weirdness）。极致古怪度为
，
其中 $f(i,\, j)$ 表示将原数组 $a$ 中下标在区间 $[i, j]$ 内（含端点）的所有元素全部删除后所得新数组的古怪度；即新数组为 $[a_1,\, \dots,\, a_{i-1},\, a_{j+1},\, \dots,\, a_n]$。

由于 5 岁的小男孩还不会编程，亚辛请求你帮忙计算给定数组 $a$ 的极致古怪度！

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.

输入的第一行包含一个整数 $n$（$1 \leq n \leq 200\,000$）—— 表示数组 $a$ 的元素个数。

下一行包含 $n$ 个整数 $a_i$（$1 \leq a_i \leq 200\,000$），其中第 $i$ 个数等于数组 $a$ 的第 $i$ 个元素。保证所有 $a_i$ 互不相同。

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

输出一行，包含数组 $a$ 的“终极怪异值”。

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.

Thus the answer is 3 + 0 + 0 + 1 + 0 + 2 = 6.

考虑第一个样例。

• $f(1,\ 1)$ 等于 3。
• $f(2,\ 2)$ 等于 1。
• $f(3,\ 3)$ 等于 2。
• $f(1,\ 2)$、$f(1,\ 3)$ 和 $f(2,\ 3)$ 均等于 0。

因此答案为 $3\ +\ 0\ +\ 0\ +\ 1\ +\ 0\ +\ 2\ =\ 6$。