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

小杨想知道有多少对 \lt l,r \gt (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。

输出一个整数，代表满足要求的 \lt l,r \gt 数量。

【样例解释 】

满足条件的 \lt l,r \gt 有\lt 3,3 \gt 和 \lt 1,5 \gt 。

【数据范围】

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

2024年GESP 6月认证C++七级真题

GESP七级数论24年6月