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:  there is integer j (l ≤ j ≤ r), such that all integers a_{l}, a_{l} + 1, ..., a_{r} are divisible by a_{j};  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.


-----Examples-----
Input
5
4 6 9 3 6

Output
1 3
2 

Input
5
1 3 5 7 9

Output
1 4
1 

Input
5
2 3 5 7 11

Output
5 0
1 2 3 4 5 



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

Difficulty: interview

Starter code:

Solutions:
n = int(input()) + 1
t = [1] + list(map(int, input().split())) + [1]
p = [True] * n
s, q = 0, list(range(1, n))
for i in range(1, n):
    if p[i]:
        a = b = i
        d = t[i]
        if d == 1: 
            s, q = n - 2, [1]
            break
        while t[a - 1] % d == 0: a -= 1
        while t[b + 1] % d == 0:
            b += 1
            p[b] = False
        d = b - a
        if d > s: s, q = d, [a]
        elif d == s != 0: q.append(a)
print(len(q), s)
print(' '.join(map(str, q)))

import math 
class SegmentTree:
    def __init__(self, data, default=0, func=lambda a,b:math.gcd(a,b)):
        """initialize the segment tree with data"""
        self._default = default
        self._func = func
        self._len = len(data)
        self._size = _size = 1 << (self._len - 1).bit_length()
 
        self.data = [default] * (2 * _size)
        self.data[_size:_size + self._len] = data
        for i in reversed(range(_size)):
            self.data[i] = func(self.data[i + i], self.data[i + i + 1])
 
    def __delitem__(self, idx):
        self[idx] = self._default
 
    def __getitem__(self, idx):
        return self.data[idx + self._size]
 
    def __setitem__(self, idx, value):
        idx += self._size
        self.data[idx] = value
        idx >>= 1
        while idx:
            self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
            idx >>= 1
 
    def __len__(self):
        return self._len
 
    def query(self, start, stop):
        if start == stop:
            return self.__getitem__(start)
        stop += 1
        start += self._size
        stop += self._size
 
        res = self._default
        while start < stop:
            if start & 1:
                res = self._func(res, self.data[start])
                start += 1
            if stop & 1:
                stop -= 1
                res = self._func(res, self.data[stop])
            start >>= 1
            stop >>= 1
        return res
 
    def __repr__(self):
        return "SegmentTree({0})".format(self.data)
class SegmentTree1:
    def __init__(self, data, default=9999999999999999999999999999999, func=lambda a,b:min(a,b)):
        """initialize the segment tree with data"""
        self._default = default
        self._func = func
        self._len = len(data)
        self._size = _size = 1 << (self._len - 1).bit_length()
 
        self.data = [default] * (2 * _size)
        self.data[_size:_size + self._len] = data
        for i in reversed(range(_size)):
            self.data[i] = func(self.data[i + i], self.data[i + i + 1])
 
    def __delitem__(self, idx):
        self[idx] = self._default
 
    def __getitem__(self, idx):
        return self.data[idx + self._size]
 
    def __setitem__(self, idx, value):
        idx += self._size
        self.data[idx] = value
        idx >>= 1
        while idx:
            self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
            idx >>= 1
 
    def __len__(self):
        return self._len
 
    def query(self, start, stop):
        if start == stop:
            return self.__getitem__(start)
        stop += 1
        start += self._size
        stop += self._size
 
        res = self._default
        while start < stop:
            if start & 1:
                res = self._func(res, self.data[start])
                start += 1
            if stop & 1:
                stop -= 1
                res = self._func(res, self.data[stop])
            start >>= 1
            stop >>= 1
        return res
 
    def __repr__(self):
        return "SegmentTree({0})".format(self.data)
n=int(input())
l=list(map(int,input().split()))
s2=SegmentTree(l)
s1=SegmentTree1(l)
s=0
e=0
d=dict()
d1=dict()
ed=[]+l[::-1]
s3=SegmentTree(ed)
s4=SegmentTree1(ed)
d2=dict()
while(s<n):
    if s in d1:
        d1[s]=e-s-1
    else:
        d1.update({s:e-s-1})
    if e==n:
        e-=1
        s+=1
    if s2.query(s,e)==s1.query(s,e):
        e+=1
    else:
        s+=1
    if s>e:
        e+=1
    if e>n-1:
        e=n
if s in d1:
    d1[s]=e-s-1
else:
    d1.update({s:e-s-1})
e=0
s=0
while(s<n):
    if s in d2:
            d2[n-1-s]=e-s-1
    else:
            d2.update({n-1-s:e-s-1})
    if e==n:
        e-=1
        s+=1
    if s3.query(s,e)==s4.query(s,e):
        e+=1
    else:
        s+=1
    if s>e:
        e+=1
    if e>n-1:
        e=n
if s in d2:
    d2[n-1-s]=e-s-1
else:
    d2.update({n-1-s:e-s-1})
ans=0
#print(d1,d2)
for j in d1:
    if j in d2: 
        if 0<=j+d1[j]<n and 0<=j-d2[j]<n and 0<=j<n and s2.query(j,j+d1[j])==s2.query(j-d2[j],j):
            d1[j]+=d2[j]
    ans=max(ans,d1[j])
for j in d2:
    ans=max(ans,d2[j])
s=0
e=s+ans
w=[] 
while(e<n):
    if s2.query(s,e)==s1.query(s,e):
        w.append(s+1)
    s+=1
    e+=1
print(len(w),ans)
print(*w,sep=' ')