Бобры-Зомби
(Время: 3 сек. Память: 16 Мб Сложность: 56%)
Вы сидите на вершине дерева с небольшой командой выживших в центре бобро-зомби апокалипсиса. На земле вас окружили N бобров-зомби, которые вот-вот сточат ствол дерева! У каждого бобра-зомби есть свой размер Si, выраженный натуральным числом.
Учёный, который недавно погиб от несчастного случая, рассказал, что, если стравить двух бобров-зомби между собой с помощью особых радиоволн, то они образуют могущественного Бобротрона, размер которого будет равен произведению размеров стравленных бобров. Последними словами учёного было уточнение, что если размер Бобротрона будет квадратом целого числа, то он будет на вашей стороне, вселит ужас в остальных бобров-зомби и заставит их убежать!
Срочно посчитайте, сколькими способами можно создать доброго Бобротрона, стравливая двух бобров-зомби!
Входные данные
Первая строка входного файла INPUT.TXT содержит целое число N – количество бобров-зомби (2 ≤ N ≤ 200 000).
Вторая строка содержит N целых чисел Si, разделённых пробелами – размеры бобров-зомби (1 ≤ Si ≤ 200 000).
Выходные данные
В выходной файл OUTPUT.TXT выведите целое число – количество пар бобров, которые смогут образовать доброго Бобротрона.
Примеры
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 4
1 4 9 16 | 6 |
| 2 | 4
2 4 6 8 | 1 |
Примечание
В первом примере подойдёт любая пара бобров.
Во втором примере подойдёт лишь пара бобров с размерами 2 и 8.
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
