区间乘积

题面描述

小杨有一个包含n个正整数的序列A=[a1,a2,...,an]。

小杨想知道有多少对<l,r>（1≤l≤r≤n）满足为完全平方数。

一个正整数x为完全平方数当且仅当存在一个正整数y使得x=y×y。

输入格式

第一行包含一个正整数n，代表正整数个数。

第二行包含n个正整数 a1,a2,...,an，代表序列 A。

输出格式

输出一个整数，代表满足要求的 <l,r>数量。

样例1

样例解释

满足条件的<l,r> 有 <3,3>和 <1,5>。

数据范围