У Семена есть массив a1, a2, ..., an, состоящий из n целых положительных чисел. Сегодня Семен попросил вас найти пару целых чисел l, r (1 ≤ l ≤ r ≤ n) такую, что выполнены следующие условия:
- существует целое число j (l ≤ j ≤ r), такое что все числа al, al + 1, ..., ar нацело делятся на aj;
- величина r - l принимает максимально возможное значение среди всех пар, для которых верно условие 1;
Помогите Семену, найдите требуемую пару чисел (l, r). Если таких пар несколько, требуется найти все.
Выходные данные
В первой строке выведите два целых числа — сколько пар нашлось и максимальное значение r - l. Во второй строке выведите все значения l из оптимальных пар в порядке возрастания.
Примечание
В первом примере пара чисел подходящая, поскольку числа 6, 9, 3 делятся на 3.
Во втором примере все числа делятся на число 1.
В третьем примере все числа простые, поэтому условиям 1 и 2 удовлетворяют только пары чисел (1, 1), (2, 2), (3, 3), (4, 4), (5, 5).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
4 6 9 3 6
|
1 3
2
|
|
2
|
5
1 3 5 7 9
|
1 4
1
|
|
3
|
5
2 3 5 7 11
|
5 0
1 2 3 4 5
|