← 返回题目列表

Codeforces · 671/C

C. 数组的终极怪异

中文机器翻译题面 查看原题

Yasin 有一个包含 n 个整数的数组 a。 Yasin 是一个 5 岁的孩子,所以他喜欢极端奇怪的东西。

Yasin 将数组的奇异性表示为所有 1 ≤ i < j ≤ n 中的最大 gcd(ai, aj) 值。当 n ≤ 1 奇异值等于 0 时,gcd(x, y) 是整数 x 和 y 的最大公约数。

他还定义了数组的终极怪异之处。最终的怪异度是 $$\sum_{i=1}^{n}\sum_{j=i}^{n}f(i,j)$$ 其中 f(i, j) 是通过删除 i 和 j 之间的所有元素获得的新数组 a 的怪异度,因此新数组是 [a1... ai - 1, aj + 1... an]。

由于 5 岁男孩不会编码,Yasin 请求您帮助找到给定数组 a 的最终怪异值!

输入

输入的第一行包含一个整数 n (1 ≤ n ≤ 200 000) - a 中的元素数量。

下一行包含 n 个整数 ai (1 ≤ ai ≤ 200 000),其中第 i 个数字等于数组 a 的第 i 个元素。保证所有ai都是不同的。

输出

打印一行,其中包含数组 a 的最终奇异值。

示例

输入 #1

3
2 6 3

输出 #1

6

注意

考虑第一个样本。

- f(1,  1) 等于 3。
- f(2,  2) 等于 1。
- f(3,  3) 等于 2。
- f(1,  2)、f(1,  3) 和 f(2,  3) 等于 0。