A9220. Pair of Numbers

Simon has an array $a_{1},a_{2},...,a_{n}$ , consisting of $n$ positive integers. Today Simon asked you to find a pair of integers $l,r$ $(1<=l<=r<=n)$ , such that the following conditions hold:

1. there is integer $j$ ( $l<=j<=r$ ), such that all integers $a_{l},a_{l+1},...,a_{r}$ are divisible by $a_{j}$ ;
2. value $r-l$ takes the maximum value among all pairs for which condition $1$ is true;

Help Simon, find the required pair of numbers $(l,r)$ . If there are multiple required pairs find all of them.

The first line contains integer $n$ ( $1<=n<=3·10^{5}$ ).

The second line contains $n$ space-separated integers $a_{1},a_{2},...,a_{n}$ $(1<=a_{i}<=10^{6})$ .

Print two integers in the first line — the number of required pairs and the maximum value of $r-l$ . On the following line print all $l$ values from optimal pairs in increasing order.

In the first sample the pair of numbers is right, as numbers $6,9,3$ are divisible by $3$ .

In the second sample all numbers are divisible by number $1$ .

In the third sample all numbers are prime, so conditions $1$ and $2$ are true only for pairs of numbers $(1,1)$ , $(2,2)$ , $(3,3)$ , $(4,4)$ , $(5,5)$ .