← 返回题目列表

Codeforces · 359/D

D. 一对数字

中文机器翻译题面 查看原题

Simon 有一个数组 a1, a2, ..., an,由 n 个正整数组成。今天 Simon 让你找到一对整数 l, r (1 ≤ l ≤ r ≤ n),使得以下条件成立:

1. 存在整数 j (l ≤ j ≤ r),使得所有整数 al, al + 1, ..., ar 都能被 aj 整除;
2. 值r - l取条件1成立的所有对中的最大值;

帮助 Simon,找到所需的数字对 (l, r)。如果有多个必需的对,则找到所有对。

输入

第一行包含整数 n (1 ≤ n ≤ 3·105)。

第二行包含 n 个空格分隔的整数 a1, a2, ..., an (1 ≤ ai ≤ 106)。

输出

在第一行打印两个整数 — 所需对的数量和 r - l 的最大值。在下面的行中,按升序打印最优对中的所有 l 值。

示例

输入 #1

5
4 6 9 3 6

输出 #1

1 3
2

输入 #2

5
1 3 5 7 9

输出 #2

1 4
1

输入 #3

5
2 3 5 7 11

输出 #3

5 0
1 2 3 4 5

注意

在第一个样本中,这对数字是正确的,因为数字 6、9、3 可以被 3 整除。

在第二个示例中,所有数字都可以被数字 1 整除。

在第三个样本中,所有数字都是质数,因此条件 1 和 2 仅对于数字对 (1, 1)、(2, 2)、(3, 3)、(4, 4)、(5, 5) 成立。