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.io.*;
import java.util.*;
import java.math.*;
 
public class Main {

    public int logTwo(int num){

        int p = 0;
        while(num != 0){
            num = (num >> 1);
            p++;
        }
        return p - 1;

    }

    public void solve() throws IOException{

        int n = in.nextInt();
        int[] aa = new int[n];
        for(int i = 0; i < n; i++){
            aa[i] = in.nextInt();
        }

        int K = 25;
        int[][] minSt = new int[n][K + 1];
        long[][] gcdSt = new long[n][K + 1];

        for(int i = 0; i < n; i++){
            minSt[i][0] = aa[i];
            gcdSt[i][0] = aa[i];
        }

        for(int k = 1; k <= K; k++){
            for(int i = 0; i + (1 << k) <= n; i++){
                minSt[i][k] = Math.min(minSt[i][k - 1], minSt[i + (1 << (k - 1))][k - 1]);
                gcdSt[i][k] = gcd(gcdSt[i][k - 1], gcdSt[i + (1 << (k - 1))][k - 1]);
            }
        }


        List<Integer> ls = new ArrayList<>();
        int res = 0;
        int l = 1, r = n + 1;
        while(l < r){

            int len = (l + r) / 2;
            List<Integer> lsForSize = new ArrayList<>();

            for(int i = 0; i <= n - len; i++){

                int end = i + len - 1;

                //out.println("Len " + len + " start " + i + " end " + end );
                int q = logTwo(len);

                //out.println("Offset from " + (end - (1 << q) + 1) + " offset " + (1 << q));
                int m =  Math.min(minSt[i][q], minSt[end - (1 << q) + 1][q]);
                long g = gcd(gcdSt[i][q], gcdSt[end - (1 << q) + 1][q]);

                
                if(m == g){
                    lsForSize.add(i);
                    
                    //out.println("got here " + lsForSize.size());
                }
            }

            //out.println("len " + len + " ok? " + lsForSize.size());

            if(lsForSize.size() != 0){
                l = len + 1;
                ls = lsForSize;
                res = len;
            }else{
                r = len;
            }
        }


        out.println(ls.size() + " " + (res - 1));
        for(int i = 0; i < ls.size(); i++){
            out.print((ls.get(i) + 1)+ " ");
        }


    }

    public BigInteger gcdBigInt(BigInteger a, BigInteger b){

        if(a.compareTo(BigInteger.valueOf(0L)) == 0){
            return b;
        }else{
            return gcdBigInt(b.mod(a), a);
        }

    }

 
    FastScanner in;
    PrintWriter out;
 
    static class FastScanner {
 
        BufferedReader br;
        StringTokenizer st;
 
        FastScanner(InputStream in) {
            br = new BufferedReader(new InputStreamReader(in));
            st = null;
        }
 
        String next() throws IOException {
            while (st == null || !st.hasMoreTokens())
                st = new StringTokenizer(br.readLine());
            return st.nextToken();
        }
 
        String nextLine() throws IOException {
            if (st == null || !st.hasMoreTokens())
                return br.readLine();
            StringBuilder result = new StringBuilder(st.nextToken());
            while (st.hasMoreTokens()) {
                result.append(" ");
                result.append(st.nextToken());
            }
            return result.toString();
        }
 
        int nextInt() throws IOException {
            return Integer.parseInt(next());
        }
 
        long nextLong() throws IOException {
            return Long.parseLong(next());
        }
 
        double nextDouble() throws IOException {
            return Double.parseDouble(next());
        }
 
    }
 
    void run() throws IOException {
        in = new FastScanner(System.in);
        out = new PrintWriter(System.out, false);
        solve();
        out.close();
    }
 
    public static void main(String[] args) throws IOException{
        new Main().run();
    }
 
    public void printArr(int[] arr){
        for(int i = 0; i < arr.length; i++){
            out.print(arr[i] + " ");
        }
        out.println();
    }
 
    public long gcd(long a, long b){
        if(a == 0) return b;
        return gcd(b % a, a);
    }

    public boolean isPrime(long num){

        if(num == 0 || num == 1){
            return false;
        }

        for(int i = 2; i * i <= num; i++){
            if(num % i == 0){
                return false;
            }
        }

        return true;
    }

    public class Pair<A, B>{
        public A x; 
        public B y;

        Pair(A x, B y){
            this.x = x;
            this.y = y;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Pair<?, ?> pair = (Pair<?, ?>) o;
            if (!x.equals(pair.x)) return false;
            return y.equals(pair.y);
        }

        @Override
        public int hashCode() {
            int result = x.hashCode();
            result = 31 * result + y.hashCode();
            return result;
        }

    }

    class Tuple{
        int x; int y; int z;
        Tuple(int ix, int iy, int iz){
            x = ix;
            y = iy;
            z = iz;
        }
    }
}
