Background

Related multiple-choice and true/false questions: https://ti.luogu.com.cn/problemset/1155.

Problem Description

Xiao Yang has a sequence $A=[a_1,a_2,\ldots,a_n]$ containing $n$ positive integers.

Xiao Yang wants to know how many pairs $\langle l,r\rangle(1\leq l\leq r\leq n)$ satisfy that $a_l\times a_{l+1}\times\ldots\times a_r$ is a perfect square.

A positive integer $x$ is a perfect square if and only if there exists a positive integer $y$ such that $x=y\times y$.

Input Format

The first line contains a positive integer $n$, representing the number of positive integers.

The second line contains $n$ positive integers $a_i$, representing the sequence $A$.

Output Format

Output an integer, representing the number of $\langle l,r\rangle$ pairs that meet the requirement.

5
3 2 4 3 2

2

Hint

Sample Explanation

The $\langle l,r\rangle$ pairs that satisfy the condition are $\langle 1,5\rangle$ and $\langle 3,3\rangle$.

Constraints

Translated by ChatGPT 5