区间乘积

题面描述

小杨有一个包含 n 个正整数的序列 A=[a¹，a² ......，aⁿ ]。

小杨想知道有多少对 <l，r> (1<=l<=r<=n) 满足a^l * a^l+1 * ........a^r 为完全平方数。

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

输入格式

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

第二行包含 n 个正整数 a¹，a² ......，aⁿ，代表序列 A。

输出格式

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

样例1

输入

5

3    2    4    3    2

输出

2

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

数据范围

对于全部数据，保证有 1 <= n <= 100000，1 <= aⁱ  <= 30