该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

问题描述

给定一个长度为 $n$ 的正整数序列$a$，求满足以下条件的三元组 $(i, j,k)$ 的数量：

1. $1 \leq i < j < k \leq n$
2. $gcd(a_i, a_j) = gcd(a_j, a_k)$（gcd即最大公约数）。

输入格式

第一行一个整数 $n$。

第二行$n$个数，表示序列$a$。

输出格式

一个整数，表示符合条件的三元组数量。

输入输出样例 #1

输入 #1

4
3 6 12 9

输出 #1

2

样例1解释

只有三元组（1，2，4）和（1，3，4）满足要求。

说明/提示

对20%的数据，$3 \leq n \leq 10^2$。

对100%的数据，$3 \leq n \leq 10^5$，$1 \leq a_i \leq 10^6$。