A71623. 区间乘积

小杨有一个包含 n 个正整数的序列 A=[a_1,a_2,...,a_n]。

小杨想知道有多少对 < l,r > (1 \le l \le r \le n )满足 a_l \times a_{l+1} \times ...\times a_r 为完全平方数。

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

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

第二行包含 n 个正整数 a_1,a_2,...,a_n ，代表序列 A。

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

【样例解释】

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

【数据范围】

对于全部数据，保证有 1 \le n \le 10^5,1 \le a_i \le 30 。