Cerința

Se dau n numere naturale. Aflați numărul subsecventelor care au produsul pătrat perfect.

Date de intrare

Programul citește de la tastatură numărul n, iar apoi n numere naturale, separate prin spații.

Date de ieșire

Programul va afișa pe ecran numărul subsecventelor care respectă condiția.

Restricții și precizări

• 1 ≤ n ≤ 100.000
• cele n numere citite vor fi mai mici decât 300

Exemplu:

Intrare

5
1 2 4 8 16

Ieșire

7