Geometric Progression

Time limit1sMemory limit1024 MB

Summary

Count index triples i<j<k in a strictly increasing array with values up to 1e6 where a_i times a_k equals a_j squared.

Problem

bobo loves geometric progressions! So he wants to know the number of geometric progressions of length $3$ in a sequence $a_1, a_2, \dots, a_n$ .

That is to say, count the number of $(i, j, k)$ where $i < j < k$ and $a_i \times a_k = a_j^2$ .

The first line contains an integer $n$ ( $1 \leq n \leq 1000000$ ).

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ( $1 \leq a_1 < a_2 < \dots < a_n \leq 1000000$ ).

A single integer denotes the number of geometric progressions.