Count Perfect Square Subarrays

You are given a sequence of n positive integers \(A = [a_1,a_2,\ldots,a_n]\). Your task is to count the number of pairs \(\langle l, r\rangle\) (where \(1 \le l \le r \le n\)) such that the product \(a_l \times a_{l+1} \times \ldots \times a_r\) is a perfect square.

A positive integer \(x\) is said to be a perfect square if and only if there exists a positive integer \(y\) satisfying \(x = y \times y\).

Hint: A number is a perfect square if in its prime factorization, every prime factor appears with an even exponent. You may use this property to optimize your solution.

inputFormat

The first line contains a single integer \(n\) representing the number of elements in the sequence. The second line contains \(n\) positive integers \(a_1, a_2, \ldots, a_n\) separated by spaces.

outputFormat

Output a single integer representing the number of pairs \(\langle l, r\rangle\) such that the product \(a_l \times a_{l+1} \times \ldots \times a_r\) is a perfect square.

sample

3
1 1 1

6