题目链接

题意

已知一个长度为 $n$ 的排列 $p$。

求有多少对数 $(i,j)$，满足 $1\le i\le j\le n$ 且 $\gcd(i,j) \ne 1$ 且 $\gcd(p_i,p_j) \ne 1$。

输入格式

第一行一个整数 $n$。

第二行 $n$ 个整数，表示排列 $p$。

输出格式

一行一个数，表示答案。

样例

6
5 1 3 2 4 6

6

12
1 2 3 4 5 6 7 8 9 10 11 12

32

数据范围

$1\le n\le 2\times 10^5$