Problem Background

The original time limit was 1.5 seconds.
Due to the difficulty in passing hack data, it has been changed to 10 seconds.

Problem Description

You are given a sequence of positive integers \(a_1, a_2, \ldots, a_n\). Your task is to determine how many subarrays have a product that is a perfect square. Specifically, you need to find the number of pairs \((l, r)\) (where \(1 \le l \le r \le n\)) such that the product \(\prod_{i = l}^{r} a_i\) is a perfect square.

Input Format

The first line contains an integer \(n\) representing the number of elements.
The next line contains \(n\) integers, representing \(a_1, a_2, \ldots, a_n\).

Output Format

Output a single integer representing the number of subarrays whose product is a perfect square.
Next, output these subarrays in lexicographical order, i.e., sorted by \(l\) first and then by \(r\). If there are more than \(10^5\) such subarrays, output the first \(10^5\) only.

Sample Input and Output

Sample Input #1

10
1 2 3 4 6 8 9 12 16 18

Sample Output #1

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

Sample Input #2

3
999999999999999956000000000000000363 999999999999999844000000000000004059 999999999999999866000000000000001353

Sample Output #2

1
1 3

Notes

[Sample #2 Explanation]

In the second sample, the three numbers are \(10^{18} - 11\), \(10^{18} - 33\), and \(10^{18} - 123\), which are pairwise multiplied.

[Sample #3]

See the attached files square/square3.in and square/square3.ans.
This sample satisfies the conditions for test points 4 through 6.

[Sample #4]

See the attached files square/square4.in and square/square4.ans.
This sample satisfies the conditions for test points 11 through 14.

[Sample #5]

See the attached files square/square5.in and square/square5.ans.
This sample satisfies the conditions for test points 18 through 20.

[Data Range]

For all data, it is guaranteed that \(1 \le n \le 3 \times 10^5\) and \(1 \le a_i \le 10^{36}\).

The specific ranges are as follows:

见题面 Input 部分

见题面 Output 部分