A93173.「SNOI2024」平方数

你有一个正整数序列 $a_1, a_2, \dots, a_n$。请问有多少个区间的乘积是完全平方数。也就是有多少对 $(l, r) (1\leq l\leq r \leq n)$，满足 $\prod_{i=l}^r a_i$ 是完全平方数。

第一行一个整数 $n$ 表示数字个数。

接下来一行，每行 $n$ 个数，表示 $a_1, a_2, \dots, a_n$。

输出一个整数，表示有多少对区间的乘积是完全平方数。

接下来按照字典序输出这些区间，也就是按照 $l$ 从小到大输出，如果有多个 $l$ 相同的区间，按照 $r$ 从小到大输出。如果区间个数超过 $10^5$ 个，输出前 $10^5$ 个即可。

对于所有的数据，保证 $1\leq n \leq 3\times 10^5$, $1 \leq a_i\leq 10^{36}$。

具体如下：

测试点编号	$n\leq$	$a_i\leq$
$1\sim3$	$1000$	$10^4$
$4\sim6$	$10^5$	$10^6$
$7\sim10$	$100$	$10^{36}$
$11\sim14$	$1000$	$10^{36}$
$15\sim17$	$10^5$	$10^{36}$
$18\sim20$	$3\times 10^5$	$10^{36}$