Simon has an array a1, a2, ..., an, 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 al, al + 1, ..., ar are divisible by aj; 
  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·105).

The second line contains n space-separated integers a1, a2, ..., an (1 ≤ ai ≤ 106).

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).
import java.util.*;
import java.io.*;

public class Main{

    BufferedReader in;
    StringTokenizer str = null;
    PrintWriter out;

    private String next() throws Exception{
    	while (str == null || !str.hasMoreElements())
    	    str = new StringTokenizer(in.readLine());
    	return str.nextToken();
    }
    
    private int nextInt() throws Exception{
	return Integer.parseInt(next());
    }
    
    SparseTableMin minTree;
    SparseTableGcd gcdTree;
    //Random rnd;
    
    public void run() throws Exception{
    	in = new BufferedReader(new InputStreamReader(System.in));
    	out = new PrintWriter(System.out);
	
	//rnd = new Random();
	
	int n = nextInt();
	int []a = new int[n];
	for(int i=0;i<n;i++) a[i] = nextInt();
	//System.out.println(Arrays.toString(a));
	minTree = new SparseTableMin(a);
	gcdTree = new SparseTableGcd(a);
	//System.out.println(minTree.min(1, 2));
	//System.out.println(gcdTree.gcd(1, 2));
	/*
	for(int i=0;i<10;i++){
	    int l = rnd.nextInt(n), r = rnd.nextInt(n);
	    if (l > r){
		int t = l;
		l = r;
		r = t;
	    }
	    
	    System.out.println(l + " " + r + " " + min.gcd(l, r));
	}
	*/
	
	int max = 0;
	Set<Integer> ans = new HashSet<Integer>();
	for(int i=0;i<n;i++){
	    int left = findLeft(0, i, a[i]);
	    int right = findRight(i, n-1, a[i]);
	    
	    //System.out.println(a[left] + " " + a[i] + " " + a[right]);
	    //System.out.println(left + " " + i + " " + right);
	    
	    if (right - left > max){
		max = right - left;
		ans.clear();
		ans.add(left+1);
	    }else if (right - left == max){
		ans.add(left+1);
	    }
	}
	
	out.println(ans.size() + " " + max);
	int []r = new int[ans.size()];
	int yk = 0;
	for(int i : ans) r[yk++] = i;
	Arrays.sort(r);
	for(int i : r)
	    out.print(i + " ");
	out.println();
        out.close();
    }
    
    private int findLeft(int tl, int tr, int x){
	int l = tl - 1, r = tr + 1;
	
	while(r - l > 1){
	    int m = l + (r-l)/2;
	    if (minTree.min(m, tr) == gcdTree.gcd(m, tr)){
		r = m;
	    }else{
		l = m;
	    }
	}
	
	return r;
    }
    
    private int findRight(int tl, int tr, int x){
	int l = tl-1, r = tr+1;
	
	while(r - l > 1){
	    int m = l + (r - l)/2;
	    if (minTree.min(tl, m) == gcdTree.gcd(tl, m)){
		l = m;
	    }else{
		r = m;
	    }
	}
	
	return l;
    }
    
    class SparseTableMin{
	int m[][];
	int []a;
	public SparseTableMin(int []a){
	    int n = a.length;
	    this.a = a;
	    
	    int log = log(n);
	    m = new int[n][log+1];
	    for(int i=0;i<n;i++) m[i][0] = i;
	    for(int i=1;i<=log;i++){
		for(int j=0;j+(1<<i)<=n;j++){
		    if (a[m[j][i-1]] <= a[m[j+(1<<(i-1))][i-1]]){
			m[j][i] = m[j][i-1];
		    }else{
			m[j][i] = m[j+(1<<(i-1))][i-1];
		    }
		}
	    }
	    /*
	    for(int i=0;i<n;i++){
		for(int j=0;j<=log;j++){
		    System.out.print(m[i][j]+ " ");
		}
		System.out.println();
	    }
	    */
	}
	
	public int min(int l, int r){
	    if (l == r) return a[m[l][0]];
	    int k = log(r - l + 1);
	    //System.out.println(k);
	    //System.out.println(m[l][k] + " " + m[r-(1<<k)+1][k]);
	    return Math.min(a[m[l][k]], a[m[r-(1<<k)+1][k]]);
	}
	
	private int log(int x){
	    int c = 1;
	    while((1<<c) < x) c++;
	    if ((1<<c) != x) c--;
	    return c;
	}
    }
    
    class SparseTableGcd{
	int [][]m;
	int []a;
	
	public SparseTableGcd(int []a){
	    int n = a.length;
	    this.a = a;
	    
	    int log = log(n);
	    m = new int[n][log+1];
	    for(int i=0;i<n;i++) m[i][0] = a[i];
	    for(int i=1;i<=log;i++){
		for(int j=0;j+(1<<i)<=n;j++){
		    m[j][i] = _gcd(m[j][i-1], m[j+(1<<(i-1))][i-1]);
		}
	    }
	}
	
	public int gcd(int l, int r){
	    int k = log(r - l + 1);
	    //System.out.println(l + " " + r + " " + k);
	    return _gcd(m[l][k], m[r-(1<<k)+1][k]);
	}
	
	private int _gcd(int a, int b){
	    return (b == 0) ? a : _gcd(b, a%b);
	}
	
	private int log(int x){
	    int c = 1;
	    while((1<<c) < x) c++;
	    if ((1<<c) != x) c--;
	    return c;
	}
    }

    

    public static void main(String args[]) throws Exception{
	new Main().run();
    }
}