Đại gia phố núi BK đã xin phép được khai thác một khu rừng trồng lấy gỗ làm nhà sàn. Khu rừng của anh có tất cả \(n\) cây. Cây thứ \(i\) có chiều cao là \(a[i]\). Để thuận lợi cho việc chặt lấy gỗ, anh cần chọn ra một số cây liên tiếp bắt đầu từ vị trí \(l\) đến \(r\) (\(1 ≤ l ≤ r ≤ n\)) thỏa mãn điều kiện sau:

• Tồn tại 1 vị trí \(j\) (\(l ≤ j ≤ r\)) sao cho với mọi cây \(i\) (\(l ≤ i ≤ r\)) thì \(a[i]\) đều chia hết cho \(a[j]\).
• Tìm ra các cặp \(l,r\) thỏa mãn điều kiện trên sao cho \(r-l\) lớn nhất.

Yêu cầu:

• Cho 1 dãy \(a\) gồm \(n\) số nguyên dương. Hãy tìm giá trị \(r - l\) thỏa mãn điều kiện và in ra các giá trị \(l\) của những cặp số đó.

Input:

• Dòng đầu tiên chứa số nguyên dương \(n\).
• Dòng thứ hai chứa \(n\) số gồm các số nguyên dương có giá trị nhỏ hơn \(10^6\).

Output:

• Dòng đầu tiên in ra số \(k\) là số các cặp (\(l,r\)) thỏa mãn điều kiện và giá trị \(r-l\) lớn nhất cách nhau bởi 1 dấu cách .
• Dòng thứ hai in ra \(k\) số là các giá trị \(l\) của các cặp số được sắp xếp từ nhỏ đến lớn.

Scoring

• Subtask \(1\) (\(70\%\) số điểm): \(n ≤ 10^3\).
• Subtask \(2\) (\(30\%\) số điểm): \(n ≤ 5\times 10^5\).

5
4 6 9 3 6

1 3
2