CF1780F.Three Chairs

有一天，Kira 找到了 $n$ 个来自 Morioh 的朋友，并决定把他们聚集在一张桌子旁，进行一次平静的交谈。第 $i$ 个朋友的身高为 $a_i$。碰巧的是，每个朋友的身高都是唯一的。

不幸的是，Kira 家里只有 $3$ 把椅子，显然无法让所有朋友都坐下！所以，Kira 只能邀请其中 $3$ 个朋友。

但事情并没有那么简单！如果被邀请的朋友中身高最低和最高的两个人的身高不是互质的，那么这些朋友就会互相捉弄，这会让 Kira 非常生气。

Kira 很好奇，有多少种方法可以选择 $3$ 个朋友，使得他们不会互相捉弄？如果有一个朋友被邀请的方式不同于另一个方式，则认为这两种方式是不同的。

形式化地说，如果 Kira 邀请了朋友 $i$、$j$ 和 $k$，那么应满足：$\gcd(\min(a_i, a_j, a_k), \max(a_i, a_j, a_k)) = 1$，其中 $\gcd(x, y)$ 表示 $x$ 和 $y$ 的最大公约数。

Kira 不太擅长计算机科学，所以他请你帮忙计算有多少种邀请朋友的方法。

第一行包含一个整数 $n$（$3 \le n \le 3 \cdot 10^5$），表示 Kira 的朋友数量。

第二行包含 $n$ 个互不相同的整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 3 \cdot 10^5$），表示 Kira 的朋友的身高。

输出一个整数，表示邀请三位朋友的方案数。

在第一个样例中，只有一种方式符合要求：邀请朋友 $1$、$2$ 和 $3$。此时 $1 < 2 < 3$，且 $1$ 和 $3$ 互质。

由 ChatGPT 4.1 翻译