Counting Squareful Intervals

You are given a sequence of positive integers \(a_1, a_2, \ldots, a_n\). Your task is to count the number of intervals (subarrays) such that the product of all numbers in the interval is a perfect square. In other words, count the number of pairs \((l, r)\) (\(1 \le l \le r \le n\)) such that

\[ \prod_{i=l}^{r} a_i \text{ is a perfect square.} \]

A number is a perfect square if all exponents in its prime factorization are even. Note that 1 (\(=1^2\)) is considered a perfect square.

inputFormat

The first line contains an integer \(n\) which represents 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 which is the number of intervals \((l, r)\) such that the product \(\prod_{i=l}^{r} a_i\) is a perfect square.

sample

1
1

1