3.2 编程题 2
试题名称：区间乘积
时间限制：1.0 s
内存限制：512.0 MB
3.2.1 题面描述
小杨有一个包含n个正整数的序列A=[a1,a2,…,an]。
小杨想知道有多少对＜l,r＞(1≤l≤r≤n) 满足al×al+1×…×ar为完全平方数。
一个正整数x为完全平方数当且仅当存在一个正整数y使得x=y×y。
3.2.2 输入格式
第一行包含一个正整数n，代表正整数个数。
第二行包含n个正整数a1,a2,…,an，代表序列A。
3.2.3 输出格式
输出一个整数，代表满足要求的＜l,r＞数量。
3.2.4 样例1
3.2.5 样例解释
满足条件的＜l,r＞有＜3,3＞和＜1,5＞。
3.2.6 数据范围
对于全部数据，保证有1≤n≤105,1≤ai≤30。
