Problem Description

Xiaolan casually wrote down an array $\{a_1, a_2,\cdots, a_n\}$ containing $n$ positive integers. He found that he can easily count how many ordered pairs $(i, j)$ satisfy that $a_j$ is a divisor of $a_i$. Therefore, he defines an integer pair $(x_1, y_1)$ to be a “divisor” of another integer pair $(x_2, y_2)$ if and only if $x_1$ and $y_1$ are divisors of $x_2$ and $y_2$, respectively. He wants to know how many ordered quadruples $(i, j, k, l)$ satisfy that $(a_i, a_j)$ is a divisor of $(a_k, a_l)$, where $i, j, k, l$ are all distinct.

Input Format

The first line contains a positive integer $n$.
The second line contains $n$ positive integers $a_1, a_2,\cdots, a_n$, separated by a single space.

Output Format

Output one line containing an integer representing the answer.

5
3 6 2 2 7

4

Hint

Quadruple $(1, 4, 2, 3)$: $(3, 2)$ is a divisor of $(6, 2)$.
Quadruple $(1, 3, 2, 4)$: $(3, 2)$ is a divisor of $(6, 2)$.
Quadruple $(4, 1, 3, 2)$: $(2, 3)$ is a divisor of $(2, 6)$.
Quadruple $(3, 1, 4, 2)$: $(2, 3)$ is a divisor of $(2, 6)$.

Constraints:
For $20\%$ of the testdata, $n \le 50$.
For $40\%$ of the testdata, $n \le 10^4$.
For all testdata, $1 \le n \le 10^5$ and $1 \le a_i \le 10^5$.

Input Format

Output Format

Translated by ChatGPT 5