We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. All Contests
  2. HourRank 2
  3. Square Segments

Square Segments

Debbie received an array as her birthday present. She wants to calculate the number of square segments in her array. A square segment is a segment of the array where the product of those numbers is a square.

For example: Array has a segment that is a square segment because

Can you help Debbie find the number of square segments?

Input Format

The first line contains , the size of the array.
The second line contains integers. The integer is .

Constraints


Output Format

Print the number of square segments in the array.

Sample Input 1

4
3 4 4 3

Sample Output 1

4

Sample Input 2

5
7 1 8 2 9

Sample Output 2

6

Explanation

In array , the square segments are:
, , and .

In array , the square segments are:
, , , , and .