D. Пара чисел
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

У Семена есть массив a1, a2, ..., an, состоящий из n целых положительных чисел. Сегодня Семен попросил вас найти пару целых чисел l, r (1 ≤ l ≤ r ≤ n) такую, что выполнены следующие условия:

  1. существует целое число j (l ≤ j ≤ r), такое что все числа al, al + 1, ..., ar нацело делятся на aj;
  2. величина r - l принимает максимально возможное значение среди всех пар, для которых верно условие 1;

Помогите Семену, найдите требуемую пару чисел (l, r). Если таких пар несколько, требуется найти все.

Входные данные

В первой строке записано целое число n (1 ≤ n ≤ 3·105).

Во второй строке записаны n целых чисел через пробел a1, a2, ..., an (1 ≤ ai ≤ 106).

Выходные данные

В первой строке выведите два целых числа — сколько пар нашлось и максимальное значение r - l. Во второй строке выведите все значения l из оптимальных пар в порядке возрастания.

Примеры
Входные данные
5
4 6 9 3 6
Выходные данные
1 3
2
Входные данные
5
1 3 5 7 9
Выходные данные
1 4
1
Входные данные
5
2 3 5 7 11
Выходные данные
5 0
1 2 3 4 5
Примечание

В первом примере пара чисел подходящая, поскольку числа 6, 9, 3 делятся на 3.

Во втором примере все числа делятся на число 1.

В третьем примере все числа простые, поэтому условиям 1 и 2 удовлетворяют только пары чисел (1, 1), (2, 2), (3, 3), (4, 4), (5, 5).