Background

The original time limit was 1.5 s.

Because it was hard to pass due to hack testdata, it was changed to 10 s.

Problem Description

You are given a sequence of positive integers $a_1, a_2, \ldots, a_n$. How many subarrays have a product that is a perfect square. In other words, how many pairs $(l, r)$ ($1 \le l \le r \le n$) satisfy that $\prod_{i = l}^{r} a_i$ is a perfect square.

Input Format

The first line contains an integer $n$, the number of integers.
The next line contains $n$ integers, $a_1, a_2, \ldots, a_n$.

Output Format

Output one integer, the number of subarrays whose product is a perfect square.
Then output these subarrays in lexicographical order, i.e., output by increasing $l$.
If multiple subarrays have the same $l$, output them by increasing $r$. If the number of subarrays exceeds ${10}^5$, output only the first ${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

Hint

[Explanation for Sample #2]

In the second sample, the three numbers are ${10}^{18} - 11, {10}^{18} - 33, {10}^{18} - 123$, and every pairwise product is computed.

[Sample #3]

See the attachments square/square3.in and square/square3.ans.

This sample satisfies the constraint limits of test points $4 \sim 6$.

[Sample #4]

See the attachments square/square4.in and square/square4.ans.

This sample satisfies the constraint limits of test points $11 \sim 14$.

[Sample #5]

See the attachments square/square5.in and square/square5.ans.

This sample satisfies the constraint limits of test points $18 \sim 20$.

[Constraints]

For all testdata, it is guaranteed that $1 \le n \le 3 \times {10}^5$, $1 \le a_i \le {10}^{36}$.

Specifically:

Translated by ChatGPT 5