Almat Kenen

Есеп №1.

Есеп A. Керемет сыйлық

Ограничение по времени:

1 second

Ограничение по памяти:

256 megabytes

Жақында Темірланның туған күні болды. Ең қызық сыйлықты оның досы Айсұлтан жасады. Айсұлтан Темірланның керемет сандарды ұнататынын біледі. Айсұлтанның ойынша, белгілі бір сан кез келген басқа бір бүтін санның квадратына тең болса, ол сан керемет сан деп есептелінеді. Мысалы, $0$, $9$, $121$ — керемет сандар, ал $50$, $3$, $12$ — керемет сандар емес. Айсұлтанда қазір $n$ бүтін саннан тұратын массив бар — $a_1, a_2, a_3, ..., a_n$. Сыйлық жасау үшін, осы тізбектен Айсұлтан екі сан $a_j$ и $a_i$ ($j < i$) алып, олардың көбейтіндісінің керемет сан бола алуын тексереді. Егер де, көбейтінді сан $a_j * a_i$ керемет болса, онда Айсұлтан көбейтіндіні Темірланға сыйлай алады деген сөз. Айсұлтан сыйлықты неше түрлі жолмен жасай алатынын анықтаңыз. Басқаша айтқанда, тізбектен $(a_j, a_i)$ жұптарының арасында $j < i$ болатын және $a_j * a_i$ көбейтіндісі керемет сан болатын жұптардың санын табыңыз.

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

Бірінші жолда тек $n$ берілген — тізбектің ұзындығы $(1 \le n \le 10^3)$. Екінші жолда бос орын арқылы жазылған $n$ бүтін саннан тұратын тізбек $a_1, a_2, a_3, ..., a_n$ берілген — Айсұлтанның тізбегі $(-1000 \le a_i \le 1000)$.

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

Тек бір сан, яғни, Айсұлтанның неше жолмен сыйлық жасай алатынын шығаруыңыз керек.

Примеры:

Вход

4
1 0 1 1

Ответ

Вход

2
-8 -2

Ответ

Вход

3
1 16 4

Ответ

Вход

1
0

Ответ

Замечание

Бұл есеп 3 бөлімнен тұрады:

$0 \le a_i \le 1$ барлық $1 \le i \le n$ үшін.
$n = 2$, $-1000 \le a_i \le 1000$.
Есептің берілгеніндегі шарттар.

Бірінші мысалда 6 жұптың барлығының көбейтіндісі 0 немесе 1 санының квадраты болып табылады. Екінші мысалда тек бір жұптың көбейтіндісі ережеге сәйкес — бүтін санның квадраты болатын 16 саны. Үшінші мысалда (1, 16), (1, 4), (16, 4) жұптарының барлығының көбейтіндісі бүтін санның квадраты болып табылады. Төртінші мысалда сыйлық құрай алатын бір де бір жұп жоқ. ( Almat Kenen )
комментарий/решение(8) олимпиада