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.

Input

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})$.

Output

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.

Note

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)$.