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) 成立。