Coprime triples

Time limit2sMemory limit512 MB

Summary

Count index triples i < j < k whose three values have gcd 1, with values up to 10^6 and n up to 10^5.

Level: Medium7 of 10
Topics: Number theory, Combinatorics, Math, Dynamic programming
Solved: No attempts yet

Problem

You are given a sequence $a_1, a_2, \dots, a_n$ of length $n$ .

Write a program that counts the triples $(i, j, k)$ with $1 \le i < j < k \le n$ and $\gcd(a_i, a_j, a_k) = 1$ , where $\gcd$ is the greatest common divisor.

The same value may appear several times, and triples are distinguished by their indices, not by their values.

Input

The first line contains the length $n$ ( $1 \le n \le 10^5$ ).

The second line contains $a_1, a_2, \dots, a_n$ ( $1 \le a_i \le 10^6$ ), separated by spaces.

Output

Print the number of triples $(i, j, k)$ that satisfy the condition on the first line.

Examples2

Example 1
Input
```
4
1 2 3 4
```
Expected output
```
4
```
Example 2
Input
```
3
2 4 6
```
Expected output
```
0
```