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。