区间乘积
时间限制:1.0 s
内存限制:512.0 MB
题面描述
小杨有一个包含 n 个正整数的序列A=[a1,a2,...,an]。
小杨想知道有多少对<l,r>(1≤l≤r≤n) 满足al×al+1×...×ar为完全平方数。
一个正整数 x 为完全平方数当且仅当存在一个正整数 y 使得x=y×y。
输入格式
第一行包含一个正整数n,代表正整数个数。
第二行包含 n 个正整数a1,a2,...,an,代表序列A。
输出格式
输出一个整数,代表满足要求的 <l,r>数量。
输入样例
输出样例
样例解释
满足条件的 <l,r> 有<3,3> 和<1,5>。
数据范围

对于全部数据,保证有1≤n≤105,1≤ai≤30。