背景

GESP七级真题(202406)

描述

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

⼩杨想知道有多少对$< l, r> ( 1 \le l, 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>$ 数量。

样例

5
3 2 4 3 2

2

样例解释

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

数据规模

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

限制

时间限制：1.0 s

空间限制：512.0 MB