Задачка A. Крутой подарокИмя входного файла: стандартный вводИмя выходного файла:

Задачка A. Крутой подарок
Имя входного файла: стандартный ввод
Имя выходного файла: стандартный вывод
Ограничение по медли: 1 секунда
Ограничение по памяти: 256 мегабайт
У Темирлана не так давно был денек рождения. Из его приятелей самый уникальный подарок решил
сделать его друг, Айсултан. Айсултан знает, что Темирлан любит крутые числа. Число называется
крутым, если оно является квадратом целого числа. К примеру, 0, 9, 121 крутые числа; а 50, 3,
12 не крутые числа.
В распоряжении Айсултана есть последовательность из n целых чисел a1, a2, a3, ..., an. Чтоб
сообразить подарок, Айсултан берет два числа из этой последовательности aj и ai таких, что j lt; i
и если число aj ai является крутым, то он даст творенье этих двух чисел Темирлану.
Помогите осознать Айсултану, сколькими методами он может это сделать. Формально, найдите
количество пар чисел (aj , ai) таких, что j lt; i и творенье aj ai является крутым числом.
Формат входных данных
Первая строчка входных данных содержит одно число n размер последовательности Айсултана
(1 n 103
).
2-ая строчка входных данных содержит n целых чисел a1, a2, a3, ..., an через пробел последовательность
Айсултана (1000 ai 1000).
Формат выходных данных
В единственной строке выведите одно число ответ на задачу.
Примеры
стандартный ввод стандартный вывод
4
1 0 1 1
6
2
-8 -2
1
3
1 16 4
3
1
0
0
Замечание
Данная задачка содержит 3 подзадачи.
1. 0 ai 1 для всех 1 i n.
2. n = 2, 1000 ai 1000.
3. Ограничения из условия.
В первом образце всего существует 6 пар чисел и все они являются квадратами числа 0 либо 1.
Во втором примере единственная пара при произведении дает 16, что является квадратом целого
числа.
В 3-ем образце все три пары (1, 16), (1, 4), (16, 4) в произедении дают квадрат целого числа.
В четвертом образце нет пар.