23128번 - Math 다국어

문제

You are given an array $a$ of $n$ distinct positive integers. Find the number of pairs $(i, j)$ with 1ドル \le i, j \le n$ for which the number $a_i^2 + a_j$ is a square of an integer.

입력

The first line of the input contains a single integer $n$ (1ドル \le n \le 10^6$), the size of the array.

The second line of the input contains $n$ distinct positive integers $a_1, \ldots, a_n$ (1ドル \le a_i \le 10^6$).

출력

Output a single integer: the answer to the problem.

제한

힌트

In the example, there are two such pairs, corresponding to 1ドル^2 + 3 = 4 = 2^2$ and 2ドル^2 + 5 = 9 = 3^2$.