小杨有一个包含 n 个正整数的序列 A=[a_1,a_2,\ldots,a_n]。
小杨想知道有多少对 \langle l,r\rangle(1\leq l\leq r\leq n) 满足 $al\times a{l+1}\times\ldots\times a_r$ 为完全平方数。
一个正整数 x 为完全平方数当且仅当存在一个正整数 y 使得 x=y\times y。
第一行包含一个正整数 n，代表正整数个数。
第二行包含 n 个正整数 a_i，代表序列 A。
输出一个整数，代表满足要求的 \langle l,r\rangle 数量。
5 3 2 4 3 2
2
满足条件的 \langle l,r\rangle 有 \langle 1,5\rangle 和 \langle 3,3\rangle。
| 子任务编号 | 数据点占比 | n | a_i |
|---|---|---|---|
| 1 | 20\% | \leq 10^5 | 1\leq a_i\leq 2 |
| 2 | 40\% | \leq 100 | 1\leq a_i\leq 30 |
| 3 | 40\% | \leq 10^5 | 1\leq a_i\leq 30 |
GESP