区间乘积

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

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

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

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

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

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

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