Migrated from Lutece 1572 Espec1al Triple

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

In mathematics, a geometric progression, also known as a geometric sequence, is a sequence of numbers where each term after the first is found by multiplying the previous one by a fixed, non-zero number called the common ratio.

For example, the sequence $2, 6, 18, 54, \dots$ is a geometric progression with common ratio $3$. Similarly $10, 5, 2.5, 1.25, \dots$ is a geometric sequence with common ratio $0.5$.

Now you are given $N$ numbers $x_1, x_2, \dots, x_N$, there are $\binom{N}{3}$ ways to choose three numbers from them, calculate how many ways to choose three numbers such that the numbers you chosen can form a geometric sequence.

Input

The first line contains an integer $N$.

The second line contains $N$ integers $x_1, x_2, \dots, x_N$.

$1 \leq N \leq 10^6$, $1 \leq x_i \leq 10^5$.

Output

How many ways to choose three numbers such that the numbers you chosen can form a geometric sequence.

Samples

9
1 2 3 4 5 6 7 8 9

4

9
1 1 1 2 2 2 4 4 4

30

3
2 4 1

1

Resources

The 15th UESTC Programming Contest Final