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 {

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

    BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st;

    String nx() throws Exception {
        for(;st == null || !st.hasMoreTokens();){
            String k1 = in.readLine();
            if (k1 == null) return k1;
            st = new StringTokenizer(k1);
        }
        return st.nextToken();
    }

    int ni() throws Exception {
        return Integer.parseInt(nx());
    }

    long nl() throws Exception {
        return Long.parseLong(nx());
    }

    double nd() throws Exception {
        return Double.parseDouble(nx());
    }

    PrintWriter out = new PrintWriter(System.out);

    Main() throws Exception {
        solve();
        out.flush();
    }

    int n1;
    int[] l1;

    void solve() throws Exception {
        n1 = ni();
        l1 = new int[n1];
        for (int i =0 ; i < n1; i++){
            l1[i] = ni();
        }
        buildMinRMQ();
        buildGcdRMQ();
        if (rangeMin(0, n1 -1) == rangeGcd(0, n1 - 1)){
            out.println(1+" " + (n1 - 1));
            out.println(1);
            return;
        }
        int low = 1;
        int high = n1;
        for (;high - low > 1;){
            int mid = (low + high)>>1;
            boolean ok = false;
            for (int i = 0; i < n1 - mid + 1; i++){
                if (rangeMin(i, i + mid - 1) == rangeGcd(i, i + mid - 1)){
                    ok = true;
                }
            }
            if (ok){
                low = mid;
            }
            else high = mid;

        }

        int count = 0;
        StringBuilder ans1 = new StringBuilder();
        for (int i = 0; i < n1 - low + 1; i++){
            if (rangeMin(i, i + low -1) == rangeGcd(i, i + low - 1)){
                count++;
                ans1.append(i +1 + " ");;
            }
        }
        out.println(count +" "+ (low - 1));
        out.println(ans1);





    }

    int log2(int n1){
        return 31 - Integer.numberOfLeadingZeros(n1);
    }

    ArrayList<int[]> minRMQ = new ArrayList();
    ArrayList<int[]> buildMinRMQ(){
        ArrayList<int[]> fin = minRMQ;
        fin.add(l1.clone());
        int len = 2;
        for (;len <= l1.length;){

            int[] last = fin.get(fin.size() - 1);
            int[] next = new int[l1.length + 1 - len];
            int half = len >> 1;
            for (int i = 0 ; i< next.length; i++){
                next[i] = Math.min(last[i], last[i + half]);
            }
            fin.add(next);
            len *= 2;
        }
        return fin;
    }

    int rangeMin(int start, int end){
        int len = end - start + 1;
        int log2 = 31 - Integer.numberOfLeadingZeros(len);
        return Math.min(minRMQ.get(log2)[start],minRMQ.get(log2)[end - (1 << log2) + 1]);
    }

    int gcd(int n1, int n2){
        return n2 == 0? n1 : gcd(n2 , n1 % n2);
    }

    ArrayList<int[]> gcdRMQ = new ArrayList();
    void buildGcdRMQ(){
        ArrayList<int[]> fin = gcdRMQ;
        fin.add(l1.clone());
        int len = 2;
        for (;len <= l1.length;){

            int[] last = fin.get(fin.size() - 1);
            int[] next = new int[l1.length + 1 - len];
            int half = len >> 1;
            for (int i = 0 ; i< next.length; i++){
                next[i] = gcd(last[i], last[i + half]);
            }
            fin.add(next);
            len *= 2;
        }
    }
    int rangeGcd(int start, int end){
        int len = end - start + 1;
        int log2 = 31 - Integer.numberOfLeadingZeros(len);
//      px(start, end, log2);
        return gcd(gcdRMQ.get(log2)[start], gcdRMQ.get(log2)[end - (1 << log2) + 1]);
    }

    static void px(Object... l1) {
        System.out.println(Arrays.deepToString(l1));
    }
}
