Районная олимпиада по информатике 2020 года за 11 класс | Казахстанские олимпиады

Задача F. Тройки

Дан массив $a$ длины $n$, который состоит из целых натуральных чисел. Все числа в массиве различные. Вам нужно посчитать количество троек $i$, $j$, $k$, что $i \ne j$, $i \ne k$, $j \ne k$ и $a_i*a_j=a_k^2$.

Формат входного файла

В первой строке задано одно целое число $n$ $(3 <= n <= 10^5)$. В следующей строке задано $n$ целых натуральных чисел $a_1$, $a_2$, $\dots$, $a_n$ $(1 <= a_i <= 3 * 10^5)$.

Формат выходного файла

Выведите одно целое число — ответ на задачу.

Примеры

Вход

6
6 3 9 4 12 27

Выход

6