You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

原题时间限制为 1.5 s。

由于 hack 数据难以通过，改为 10 s。

题目描述

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

输入格式

第一行一个整数 $n$ 表示数字个数。
接下来一行，每行 $n$ 个数，表示 $a_1, a_2, \ldots, a_n$。

输出格式

输出一个整数，表示有多少对区间的乘积是完全平方数。
接下来按照字典序输出这些区间，也就是按照 $l$ 从小到大输出。
如果有多个 $l$ 相同的区间，按照 $r$ 从小到大输出。如果区间个数超过 ${10}^5$ 个，输出前 ${10}^5$ 个即可。

10
1 2 3 4 6 8 9 12 16 18

12
1 1
1 5
2 5
3 6
3 7
4 4
4 8
4 9
5 8
5 9
7 7
9 9

3
999999999999999956000000000000000363 999999999999999844000000000000004059 999999999999999866000000000000001353

1
1 3

提示

【样例 #2 解释】

在第二个样例中，这三个数为 ${10}^{18} - 11, {10}^{18} - 33, {10}^{18} - 123$ 两两相乘。

【样例 #3】

见附件中 square/square3.in 与 square/square3.ans。

这个样例满足测试点 $4 \sim 6$ 的条件限制。

【样例 #4】

见附件中 square/square4.in 与 square/square4.ans。

这个样例满足测试点 $11 \sim 14$ 的条件限制。

【样例 #5】

见附件中 square/square5.in 与 square/square5.ans。

这个样例满足测试点 $18 \sim 20$ 的条件限制。

【数据范围】

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

具体如下：