Problem Statement

You are given an array A of N positive integers.

The product of a subarray is said to be special if it has an odd number of positive divisors.

Count the number of contiguous subarrays whose product is special.

Input Format

• The first line contains an integer N.
• The second line contains N integers A1, A2, ..., AN.

Output Format

Print a single integer — the number of special subarrays.

Constraints

• 1 ≤ N ≤ 2 × 10^5
• 1 ≤ Ai ≤ 10^9

Sample Input

5 1 4 2 9 16

Sample Output

6

Explanation

A number has an odd number of divisors if and only if it is a perfect square.

The qualifying subarrays are:

• [1]
• [4]
• [9]
• [16]
• [1, 4]
• [4, 2, 9, 16]

Hence, the answer is 6.