Treo đèn

Trong một ngôi làng ven biển, dân làng muốn dựng một dãy cột treo đèn lồng dọc theo con đường chính.
Làng có tất cả \(n\) cây tre, cây thứ \(i\) có chiều cao \(a_i\). Trưởng làng sẽ chọn một đoạn liên tiếp các cây tre,
bắt đầu từ vị trí \(l\) đến \(r\) (\(1 \le l \le r \le n\)), sao cho tồn tại một vị trí \(j\) với \(l \le j \le r\) thỏa mãn:

• Với mọi \(i\) (\(l \le i \le r\)), ta có \(a_i\) chia hết cho \(a_j\).

Mục tiêu là tìm các cặp \((l, r)\) như trên sao cho độ dài đoạn \(r - l\) là lớn nhất.

\InputFile

• Dòng đầu chứa số nguyên dương \(n\).
• Dòng thứ hai chứa \(n\) số nguyên dương \(a_1, a_2, \dots, a_n\) với \(a_i < 10^6\).

\OutputFile

• Dòng đầu in ra hai số nguyên \(k\) và \(d\) (cách nhau bởi một dấu cách), trong đó:

• \(d\) là giá trị lớn nhất của \(r - l\),

• \(k\) là số lượng cặp \((l, r)\) thỏa mãn \(r - l = d\).

• Dòng thứ hai in ra \(k\) số nguyên là các giá trị \(l\) tương ứng của những cặp đạt \(r - l = d\), theo thứ tự tăng dần.

\Scoring

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

Example

5
4 6 9 3 6

1 3
2