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.math.*;
import java.io.*;
import java.text.DecimalFormat;
import java.math.BigInteger;
public class Main{
    static int d=20,n;
    static int mod=1000000007 ;
    static  ArrayList<ArrayList<Integer>> arr;
    static int[][] gst,mst;
    public static void main(String[] args)  throws IOException {
        s.init(System.in);        
        PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
        n=s.ni();
        int[] a=new int[n];
        for(int i=0;i<n;i++)
            a[i]=s.ni();
        sparseTable(a);
        int l = 1;
        int r = n;
        int ans = 0;
        while (l<=r){
            int mid = (l+r)/2;
            if (check(mid)){
                ans = mid;
                l = mid+1;
            }else{
                r = mid-1;
            }
        }
        ArrayList<Integer> answer = new ArrayList<Integer>(); 
        int lg = (int)(Math.log(ans) / Math.log(2));
        for (int i=0;i<n;i++){
            if (i+ans-1 >=n) break;  
            if (check(i,i+ans-1,lg)){
                answer.add(i+1);
            }
        }
        out.println(answer.size()+" "+(ans-1));
        for (int y : answer) out.print(y+" ");
    


        out.close();
    }
 
        
    public static void sparseTable(int[] a){
        gst = new int[n][d];
        mst = new int[n][d];
        for (int i=0;i<n;i++){
            gst[i][0] = mst[i][0] = a[i];
        }
        for (int i=1;i<d;i++){
            int k = 1 << (i-1);
            for (int j=0;j<n;j++){
                if (j + k >= n) break;
                gst[j][i] = gcd(gst[j][i-1], gst[j+k][i-1]);
                mst[j][i] = Math.min(mst[j][i-1], mst[j+k][i-1]);
            }
        }       
    }

    public static int gcd(int a, int b){
            if (a == 0) return b;
            return gcd(b % a, a);
    }
        
    public static boolean check(int len){
        int lg = (int)(Math.log(len) / Math.log(2));
        for (int i=0;i<n;i++){
            if (i+len-1 >=n) break;
            if (check(i,i+len-1,lg)) {
                return true;
            }
        }
        return false;
    }
    public static boolean check(int l, int r, int lg){
        int len = r - l + 1;
        int gcd = gcd(gst[l][lg],gst[r-(1<<lg) + 1][lg]);
        int min = Math.min(mst[l][lg], mst[r-(1<<lg) + 1][lg]);
        return gcd == min;
    }
        
        
   
    
       
    
    public static class s {
        static BufferedReader reader;
        static StringTokenizer tokenizer;
 
        /** call this method to initialize reader for InputStream */
        static void init(InputStream input) {
            reader = new BufferedReader(
                        new InputStreamReader(input) );
            tokenizer = new StringTokenizer("");
        }   
 
        /** get next word */
        static String ns() throws IOException {
            while ( ! tokenizer.hasMoreTokens() ) {
                //TODO add check for eof if necessary
                tokenizer = new StringTokenizer(
                    reader.readLine() );
            }
            return tokenizer.nextToken();
        }
 
        static int ni() throws IOException {
            return Integer.parseInt( ns() );
        }
    
        static double nd() throws IOException {
            return Double.parseDouble( ns() );
        }
        static long nl() throws IOException {
            return Long.parseLong( ns() );
        }
        
    }
} 