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

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

Ограничение по времени Ограничение по памяти
1 секунда 256 мегабайт

Дан массив aa длины nn, который состоит из целых натуральных чисел. Все числа в массиве различные. Вам нужно посчитать количество троек ii, jj, kk, что iji \ne j, iki \ne k, jkj \ne k и aiaj=ak2a_i*a_j=a_k^2.

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

В первой строке задано одно целое число nn (3<=n<=105)(3 <= n <= 10^5). В следующей строке задано nn целых натуральных чисел a1a_1, a2a_2, \dots, ana_n (1<=ai<=3105)(1 <= a_i <= 3 * 10^5).

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

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

Примеры

Вход

6
6 3 9 4 12 27

Выход

6