题目描述

小杨有一个包含 $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 \cdots \times a_r$ 为完全平方数。

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

输入格式

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

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

输出格式

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

输入样例 1

5
3 2 4 3 2

输出样例 1

2

样例解释 1

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

数据范围

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